DP(动态规划背包小讲).doc

DP动态规划之背包
先上题目吧:
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路:
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]};
对于第i个物品,可以选择放进背包,也可以选择不放进背包。所以选择最大的情况,用max判断那种状况是最大值。
如果不放,那当前f[i][v]=f[i-1][v];
如果放,那当前f[i][v]=f[i-1][v-c[i]]+w[i],将背包容量减去第i个物品的重量,然后再加上它的价值。
举个例子吧:假设有一共有4个物品,总容量6。
weight容量 value价值
第1个物品 1 4
第2个物品 2 6
第3个物品 3 12
第4个物品 2 7
关键代码:
for(i=1;i<=n;i++) //n=4 (物品数目)
for(v=m;v>=weight[i];v--) //m=6(背包容量)
f[v] = Max(f[v],f[v-weight[i]]+value[i]);
依次考虑将这4个物品放入背包:
第1个物品 f[6]=4 f[5]=4 f[4]=4 f[3]=4 f[2]=4 f[1]=4
第2个物品 f[6]=10 f[5]=10 f[4]=10 f[3]=10 f[2]=6
第3个物品 f[6]=22 f[5]=18 f[4]=16=f[3]=12
第4个物品 f[6]=23 f[5]=19 f[4]=16 f[3]=12 f[2]=7
但为何是这样呢?
f[v] 代表放第i物品时,容量为v的背包能放的物品最大价值。当放第1个物品时,因为第1 个物品的重量为1,所以容量为1到6的背包都可以放这个物品,即 f[v]=4;放第2个物品时,因为