动态规划算法闭包问题

Question

0/1闭包问题n=5 w={7,3,6,7,4}v={8,3,10,4,6},w=15,写出动态规化
详细过程。越具体越好

Answer 1

用m[i][j]表示当背包容量为j时选择第i,i+1,i+2,….n件物品时价值的最大值，wi表示第i件物品的重量，vi表示第i件物品的价值
考虑几种可能的情况：
1、 第i件物品的重量大于背包剩余容量（wi>j）：不选第i件物品，此时有：
m[i][j]=m[i+1][j]
2、 第i件物品的重量小于等于背包剩余容量（wi<=j）：此时可以做出两个选择，选择或者不选第i 件物品，而m[i][j]则是两种选择计算出的最优值，既：
m[i][j]=max{m[i+1][j],m[i+1][j-wi]+vi}（第一项表示不选i,第二项表示选择i）
3、 对于第一件物品的选择，若其重量大于背包容量则不选，否则选择后最大价值为该物品价值
由此可得出计算m[i][j]的递归式：

当n=5 w={7,3,6,7,4},v={8,3,10,4,6},w=15时
我们需要计算的就是m[1][15],计算顺序如下