背包DP

循环的层级顺序和内层循环的方向总结

01背包or完全背包

01背包：每个物品只能选1次或不选。

当我们计算 dp[j] 时，我们希望 dp[j - w] 是还没有放入第 i 个物品时的状态。

完全背包：每个物品可以选无数次。

当我们计算 dp[j] 时，我们希望 dp[j - w] 是可能已经放入了第 i 个物品的状态.

if 正序：
可以无数量限制的拿取物品
if 倒序：
只能计算一次当前数据

综上

01背包倒序保护现场，完全背包正序继续叠加

// 01 背包
for (int i = 1; i <= n; i++) {           // 1. 枚举物品for (int j = W; j >= w[i]; j--) {    // 2. 枚举容量 (必须倒序！)dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}
}

// 完全背包核心代码
for (int i = 1; i <= n; i++) {           // 1. 枚举物品for (int j = w[i]; j <= W; j++) {    // 2. 枚举容量 (必须正序！)dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}
}

未完待续......