shengqiang's blog

背包问题

 
  • 2017年 07月10日

##大致思路：

  • 穷举法

  1. 定义一个具有N个元素的一维数组（N表示物品数），用二进制模拟的方式代表每个物品的存放状态 将存放状态放入该一维数组中，并依次循环计算每种状态的总价值，若总重量不超过最大限度并且比之前保存的最优值大的话，则更新数据，使最优值为此次的数据；若总重量超过最大限度，则舍弃。
  2. 循环结束后，一维数组保存了所有物品的存放状态，依次即可算出最大值

  • 动态规划法

    1. 通过分析得出以下公式
     V(i,0)=V(0,j)=0
 (i,j)=V(i-1,j) jwi
  1. 分析得出如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包

如果第i个物品的重量小于背包的容量，则会有一下两种情况：

i. 如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi;

ii. 如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。

##主函数:

  1. 定义变量choice,定义状态数组Judge,初始化物品数据
  2. 提示用户输入编号选择不同的方法求解
  3. 若输入1，则调用函数Bag_Exhaustive(&good, Judge);//穷举法获得结果
  4. 若输入2，则调用函数MaxValue = Bag_Dp(N, good.weight, good.value, Judge,good.limitw);//动态规划获得结果

##Play()函数: 根据Judge数组的数据可知物品的存放状态，并打印出最终最有的总重量和总价值 ##Bag_Dp()函数： 变量i,j，以及二维数组V，并将V[i][0]赋值为0，将V[0[j]赋值为0

通过公式，V[i][j] = V[i – 1][j](j<w[i]以及V[i][j] = max(V[i – 1][j], V[i – 1][j – w[i]] + v[i])(j>=w[i])依次为二维数组每个数据赋值

如果V[i][j]>V[i –1][j]，则令x[i]为1，j=j-w[i]；否则x[i]=0

##Bag_Exhaustive()函数

  1. 定义S数组，用于存放物品状态
  2. 调用Bin(S,num)函数，返回二进制状态，并依次计算每种状态所得到的tw总质量和tv总价值，若不超过总质量，则将其与maxvalue比较，若比它大，则更新数据，使新的最优值为现在这个。

##bin(……)函数

  1. 定义进位变量carry,依次计算出s[i]中每个元素的状态，直到carry为0

##关键代码

// Bag.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdlib.h"
#define N 4
int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值

typedef struct
{
    int value[N];
    int weight[N];
    int num;
    int limitw;
}Bag;

int bin(int s[], int n)//二进制模拟运算
{
    int i, carry = 0;
    s[0] += 1;
    for (i = 0; i < n; i++)
    {
        s[i] += carry; //加上进位
        carry = s[i] / 2;//计算进位         
        s[i] %= 2; //保留0或1?
        if (carry == 0)
        {
            printf("\n方案");
            for (int j = 0; j < n; j++)
                printf("%d", s[j]);
            printf("\n");
            return 0;
        }
            
    }
    printf("\n方案");
    for (int j = 0; j < n; j++)
        printf("%d", s[j]);
    printf("\n");
    return carry;
}

void Bag_Exhaustive(Bag *g, int Judge[])//计算最优解 穷举法
{
    int i, flag;
    int S[5];/*临时状态数组*/
    double MaxValue = 0, tw, tv;
    for (i = 0; i < g->num; i++)//将数组清空 
        S[i] = 0;

    while (bin(S, g->num) == 0) //进行一次二进制模拟运算 
    {
        tw = 0;
        tv = 0;
        flag = 1;
        for (i = 0; i < g->num; i++) //选中状态 
        {
            if (S[i] == 1) //选中
            {
                tw += g->weight[i]; 
                tv += g->value[i];
                if (tw > g->limitw) //超重
                {
                    flag = 0;
                    break; //退出本次方案
                }
            }
        }
        if (flag && MaxValue < tv)
        {
            MaxValue = tv;
            for (i = 0; i < g->num; i++) //保存方案（也是更新方案）
                Judge[i] = S[i];
        }
    }
}

​

int max(int a, int b)//返回最大值
{
    if (a >= b)
        return a;
    else return b;
}

int Bag_Dp(int n, int w[], int v[], int x[], int C)//动态规划法
{
    int i, j;
    for (i = 0; i <= n; i++)//V(i,0)=V(0,j)=0
        V[i][0] = 0;
    for (j = 0; j <= C; j++)//V(i,0)=V(0,j)=0
        V[0][j] = 0;

    for (i = 0; i < n; i++)
        for (j = 0; j <= C; j++)
            if (j<w[i])
                V[i][j] = V[i - 1][j];
            else
                V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);
    j = C;
    for (i = n - 1; i >= 0; i--)//选出物品
    {
        if (V[i][j]>V[i - 1][j])
        {
            x[i] = 1;
            j = j - w[i];
        }
        else
            x[i] = 0;
    }

    for (i = 0; i < n; i++)//输出结果
    {
        for (j = 0; j <= C; j++)
            printf("%2d ", V[i][j]);
        printf("\n");

    }

    return V[n][C];//返回最优解

​

}

void Play(Bag good, int Judge[])//显示最优结果
{
    int Weight = 0, MaxValue = 0;//最优解
    for (int i = 0; i < good.num; ++i)
    {
        if (Judge[i])
        {
            printf("第%d号物品,重量:%d千克,价值:%d元\n", i + 1, good.weight[i], good.value[i]);
            Weight += good.weight[i];
            MaxValue += good.value[i];
        }
    }
    printf("\n总重量为:%d千克,总价值为:%d元\n", Weight, MaxValue);
}

int main(void)
{
    int choice;//选择方式
    int Judge[N] = { 0 };//判断物品最终是否选中状态
    Bag good = { { 42,12,40,25 },{ 7,3,4,5 },N,10 };//初始化结构体
    printf("==============================================\n");
    printf("====================背包问题==================\n");
    printf("================输入1 选择穷举法==============\n");
    printf("================输入2 选择动态规划============\n");
    printf("==============================================\n");
    printf("请输入选项<1～2>");
    while (scanf("%d", &choice) != 1 || choice >= 3 || choice <=0)
    {
        printf("输入错误，请输入选项<1～2>");
        while (getchar() != '\n');//清除缓存区，类似fflush
    }
    switch (choice)
    {
        case 1:
        {
            printf("穷举法法解决\n");
            Bag_Exhaustive(&good, Judge);//穷举法获得结果
            Play(good, Judge);//打印
            break;
        }
        case 2:
        {
            int MaxValue;
            printf("动态规划法解决\n");
            MaxValue = Bag_Dp(N, good.weight, good.value, Judge, good.limitw);//动态规划获得结果
            Play(good, Judge);//打印
            break;
        }
        default:;
    }
    system("pause");
    return 0;
}
搜索