背包问题全集

参考

花花讲0-1背包
https://www.youtube.com/watch?v&＃61;CO0r6kcwHUU&t&＃61;1312s 和
https://www.youtube.com/watch?v&＃61;rM_G4dboKhc

0-1背包

从1到N件物品迭代&＃xff0c;从W到w滚动更新dp。

完全背包

这里跟0-1背包时公式的区别是:

• 此处重量是从w迭代到W
• dp[j]更新时会用到该行的dp[j-w]&＃xff0c;这是因为它需要这一行中更小重量的结果。而0-1背包中之所以从W迭代到w&＃xff0c;是因为它需要上一行的更小重量的结果。

完全背包n次