背包DP

01背包or完全背包

01背包：每个物品只能选1次或不选。
\(n\)：物品的总个数。
\(W\)：背包的最大总容量
\(w\)：第 i 件物品的重量/体积
\(v\)：第 i 件物品的价值 (value)。
\(dp[j]\)：当容量限制为 j 时，能获得的最大价值。
当我们计算 \(dp[j]\) 时，我们希望 \(dp[j - w]\) 是还没有放入第 i 个物品时的状态。

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

复制代码

完全背包：每个物品可以选无数次。
\(n\)：物品的总个数。
\(W\)：背包的最大总容量
\(w\)：第 i 件物品的重量/体积
\(v\)：第 i 件物品的价值 (value)。
\(dp[j]\)：当容量限制为 j 时，能获得的最大价值。
当我们计算 \(dp[j]\) 时，我们希望 \(dp[j - w]\) 是可能已经放入了第 i 个物品的状态.
[code]// 完全背包核心代码for (int i = 1; i  n >> W;    for(int i = 1; i > v >> w >> m; // 注意题目输入顺序可能是 价值、重量、数量                // --- 二进制拆分核心 ---        int k = 1;        while(m >= k) {            cnt++;            nw[cnt] = k * w;            nv[cnt] = k * v;            m -= k;            k *= 2;        }        if(m > 0) {            cnt++;            nw[cnt] = m * w;            nv[cnt] = m * v;        }        // ---------------------    }    // --- 0/1 背包核心 ---    // 遍历所有拆出来的新物品    for(int i = 1; i = nw; j--) {            dp[j] = max(dp[j], dp[j - nw] + nv);        }    }    cout