01背包精讲

给定一个物品集合s={1,2,…..,n}，物品i具有重量wi和价值vi。背包能承受能承受的最大载重量不超过W。背包问题就是找到一个物品子集s‘属于s，使得maxEwi<=W。所谓01背包就是物品要么整个地选取，要么不取。

首先我们先要肯定一件事，假设子问题(i,w)的最优装载中含有物品i，则其中的子问题(i-1,w-wi)的装载方案也一定是最优的。 证明:(反证法)假设子问题(i-1,w-wi)的装载方案p不是最优的，则有一个更优的装载方案p’，将p’替换p然后在加上物品i将会比原来的最优装载价值最大，与假设矛盾。 现设定一个数组v[i,w](i代表第几个物品，w代表i物体的重量)表示将物品1到物品i的物品装入载重量为w的背包中所能获得的最大价值，即子问题(i,w)的最大价值 (1)对于物品i能够装进背包，则子问题（i,w）的最优解取决于物品i是否放进去 ①如果物品i不放进去，则有v[i,w]=v[i-1,w]。就是说i不放进去，那么容量为i的背包的价值==容量为i-1的背包的价值 ②若将物品i放进去，则有v[i,w]=v[i-1,w-wi]+vi。若i放进去，那么容量为i的背包的价值==容量为i-1的背包的价值加上第i个物品的价值 解析：相信大多数人都想不明白这句话的意思，若物品i能够放进去，那么一定是放进去后这个背包的价值肯定大于没放进去的价值大，这是错误的，假设有三个物品（1，1） （2，3）（2，2）【（物品重量，价值）】，现我们规定背包总重量限制于3，相信大家一眼就可以看出来，物品13的结合的价值没有物品12结合的价值大，自然3不放的总价值大于放的总价值，12放进去后此时背包容量已满，但倘若物品3放进去，那么背包为了能够容纳3，它必将2剔除，所以说3不放的价值大于放的价值。

v[i-1,w-wi]，i-1自然是说i的前一个物品的序列号，而w-w[i]是刚好满足放置i物品容量的前一个，这里的前不一个不是固定于下图标的斜对前，而是前一个物品的容量+当前i物品的容量刚好等于此时枚举到的w

现在为大家推一便算法，就明白了。

前提大家要先明确一件事，01背包算法精髓就是扫，假设背包容量为w，物品个数为n，那么可以假定的认为一个二维数组，行为第几个物品，第一行为第一个物品，第二行为第二个 物品，第n行为第n个物品。列为容量的多少，第一列是容量为1的背包，第二列是容量为2的背包，第三列为3，第n列为n。

给一组数据，物品号 wi vi 1 2 12 2 1 10 3 3 20 4 2 15

背包算法如下的表格所示

解析：

1.第1个[2,12]物品，背包容量为1时，2>1它进不了背包,背包容量为2时，刚好够物品容量则进入背包，所以背包容量最大价值为12;背包容量为3，4，5时1号物品都可以进入背包，所以价值均为12。 2.第2个[1,10]物品，背包容量为1时，它的前一个物品c[1][1-1]=0+10(放进第二个物品的价值)=10大于不放，所以放；背包容量为2时，对于前一个背包c[2-1][2-1]=0+12大于它的前一个容量的价值c[1][2]，所以此时对于前一阶段要放置2号物品    背包容量为3，对于前一物品c[2-1][3-1]=12,若放2号物品，则12+10>不放，所以放，而对于背包容量都为4,5时，都是放置2号物品的价值大于不放，所以都放 3.第3个[3,20]物品，背包容量为1，2时，w[3]均大于背包容量，所以不放，承接前一物品背包容量1,2的价值；当背包容量为3的时候，此时c[3-1][0]+20(放)，小于放置物品1,2的价值，所以3不放，放1,2；而对于背包容量为4的时候，c[2][1]=10（这个说明减去放置物品3的容量，此时背包中还剩下物品1）+20=30,此时的价值大于放1,2,，则放置1,3。。。。。

4.同理

int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n)//m是价值的限制,n是物品的个数
{
    int i,j,w[10],p[10];//w是容量，p是价值

    for(i=1; i<n+1; i++)
        scanf(“%d%d”,&w[i],&p[i]);
    memset(c,0,sizeof(c));
    for(i=1; i<n+1; i++)
        for(j=1; j<m+1; j++)
        {
            if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
            {
                if(p[i]+c[i-1][j-w[i]]>c[i-1][j])//i-1个背包的价值加上第i个物品的价值是否大于不放的价值
                    /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
                    /*大于上一次选择的最佳方案则更新c[i][j]*/
                    c[i][j]=p[i]+c[i-1][j-w[i]];
                else
                    c[i][j]=c[i-1][j];
            }
            else c[i][j]=c[i-1][j];
        }
    return(c[n][m]);
}

一维数组的

for(i=1;i<n+1;i++)
{
    for(j=m;j>=w[i];j--)//m是物品的价值总和
    {
         c[j]=_max(c[j],c[j-w[i]]+p[i]);
    }
}  
for(i=sum;i>=0;i--)//输出
{
         if(dp[i]<=limit) 
         {
            printf("%d\n",i);
             break;
          }
 }