0-1 背包问题

定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。
设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，

dp[i][j] = dp[i-1][j]。

第 i 件物品添加到背包中，
dp[i][j] = dp[i-1][j-w] + v。


第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
dp[i][j]=max(dp[i-1][]j),dp[i-1][j-w]+v)	

空间优化
在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物
品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，
dp[i]=maz(dp[i], dp[j-w] +v)

原版
0-1背包即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；```language


for (int num : nums) {
        for (int i = target; i >=0; i--) {
            }
        }

变种
完全背包：物品数量为无限个。即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。

for (int num : nums) {
    for (int i = num ; i <=target ; i++) {
    }
}


多重背包：物品数量有限制
多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制
其它：物品之间相互约束或者依赖  如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
```language
for (int i = 1; i <=target; i++) {
    for (int num : nums) {
            }
        }

组合问题公式
dp[i] += dp[i-num]

True、False问题公式
dp[i] = dp[i] or dp[i-num]

最大最小问题公式
dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)

规律
背包问题 总是输入一个数组/列表，与一个目标值
dp的长度一般为target+1，具体情况不同
往往dp[0]需要被赋值
return一般是dp[target]

能给我打赏么？总结不易！