背包问题

搁置已久，今天来简单讨论下背包的基础性问题

01背包

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

二维状态转移方程：$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])$
$dp[i][j]$表示前i件物品放入一个容量为j的背包可以获得的最大价值，v[i]可放可不放

一维状态转移方程：$dp[j] = max(dp[j], dp[j-w[i]] + v[i])$
dp[j]表示容量恰为j的时候的最大价值

一维01背包为什么倒序

对二维背包来讲，i各种容量下的解依赖的是没有i这个物品时的最优解，即考虑前i-1件物品所产生的最优解 对于一维背包来讲，我们优化掉了存储的维度，如果正序遍历j，那么在更新dp[j]时，dp[j-w[i]]已经被物品i更新过了，依赖关系被破坏，即在更新时，由于 $j-w[i]<j$ 会优先更新dp[j-w[i]-w[i]]，
而倒序遍历j则会保证较小的j-w[i]维持i-1次的状态，故而保证第i件物品在每次更新时不会重复使用。
（正是因为每次都是逐步考虑保证了前i次的最优解，故最终遍历到n时即保证全局最优解，即动态规划）

01背包核心代码

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

完全背包

其差别在于，完全背包不再有物品的数量限制，每件物品均有无穷件
那就好办了，我们刚刚说了之所以倒序，就是为了避免第i物品被考虑多次，那我们正着写，那就恰满足了每件物品被考虑多件的需求，我们每次从小开始遍历，在处理j的时候j-w[i]实际上已经考虑过有第i件物品情况下的最优解，依次类推即每件物品都没有了件数限制

完全背包核心代码

for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= m; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

多重背包

放上题目

B2174 完全背包B2174 完全背包

背包问题有时甚至会混淆视听
P7223 [RC-04] 01 背包(https://www.luogu.com.cn/problem/P7223)