0-1背包问题（动态规划算法）_0背包公式

0-1背包问题（动态规划算法）

一、思路

我们直接从一个实例开始。
有五件商品，如下表，vi代表它的重量，pi代表它的价值，背包容量为13。

第一步，初始化备忘录表。
当背包容量为0时：P[i,0]=0;
当没有可选商品时：P[0,c]=0。

第二步，确定计算顺序。（也可从左到右、从下到上）

第三步，根据递推公式填表。

(现在我们结合下图二维表来理解)
i=1时，P[1,c]这行表示只有物品1可选。

P[1,1]位置：c=1,v[1]=10,c<v[i],背包容量小于可选商品，表示不能选该商品，即采用递推公式中P[i-1,c]该方案。将P[0,1]=0照抄在P[1,1]上。（也就是把该位置(i)的上一行(i-1)相同位置的数值抄写下来）

P[1,2]位置~P[1,9]位置也是上面的原理。

P[1,10]位置：c=10,v[1]=10,c>=v[i],背包容量大于等于可选商品，表示能选该商品，此时我们按照递推公式比较 选择该商品 和 不选该商品 哪个方案的P(价值)更大。
选择该商品：P[i-1,c-v[i]]+p[i]=P[1-1,10-10]+p[1]=P[0,0]+24=24
不选该商品：P[i-1,c]=0
因为24>0，所以我们选择该商品。

依据上述两种情况填表即可。

当填完表后，我们知道了最大值，但怎么知道选择了哪些商品呢？
我们通过构造Rec[i,c]数组来记录是否选择该商品。
当选择商品时，Rec[i,c]=1;
当不选择商品时，Rec[i,c]=0;


我们由上图开始倒推选择了哪些商品：
Rec[5,13]=1,所以选择了商品五，13-v[5]=13-4=9(减去商品五的重量)；
Rec[4,9]=1,代表选择了商品四，9-v[4]=9-5=4(减去商品四的重量)；
Rec[3,4]=1,代表选择了商品三，4-v[3]=4-4=0(减去商品三的重量)；
此时背包已装满。

所以所选物品为五、四、三。

二、伪代码