问题总结

01背包

原始问题

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

暴力法

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是$o(2^n)$，这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

动态规划（二维数组版）

01背包

动态规划（一维滚动数组版）

滚动数组
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

注意点

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
一维dp必须先遍历物品，嵌套遍历背包容量。

2. 完全背包

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。