背包问题:
1:01背包:
状态转移方程(二维):f[i][j]=max(f[i-1][j],f[i-1][j-v]+w)
状态转移方程(一维):f[j]=max(f[j],f[j-v]+w)
2:完全背包问题:
状态转移方程(二维):f[i][j]=max(f[i-1][j],f[i][j-v]+w)
状态转移方程(一维):f[j]=max(f[j],f[j-v]+w)
二者区别:在一维时,关于体积j的遍历方向,01背包从大到小遍历体积,完全背包从小到大遍历体积。
产生区别的原因:二维方程的第二项是来源于上一层物品还是本层物品