From 74d90ca3302099a165365fdf9373aa622c1b1da4 Mon Sep 17 00:00:00 2001
From: orzcyand1317 <36555123+orzcyand1317@users.noreply.github.com>
Date: Sat, 9 Mar 2019 08:53:39 +0800
Subject: [PATCH] Update backpack.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

修了 1/3 陈年老锅。
/ 别拉着我我一定要喷这个写的人
---
 docs/dp/backpack.md | 82 ++++++++++++++++++++++++++---------------------------
 1 file changed, 40 insertions(+), 42 deletions(-)

diff --git a/docs/dp/backpack.md b/docs/dp/backpack.md
index 9d8919ef..ce3127b1 100644
--- a/docs/dp/backpack.md
+++ b/docs/dp/backpack.md
@@ -2,69 +2,67 @@
 
 在具体讲何为 "背包 dp" 前，先来看如下的例题
 
-??? note " 例题[\[USACO07DEC\]手链 Charm Bracelet](https://www.luogu.org/problemnew/show/P2871)"
-    本题题意可概括为——N 物体，放入容量为 M 的背包，要求使总价值最大。由于每个物体只有 2 种情况——取与不取，正如二进制中的 0 和 1——这类问题便被称为“0-1 背包问题”。
+??? note " [\[USACO07 DEC\]Charm Bracelet](https://www.luogu.org/problemnew/show/P2871)"
+    题意概要：有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
+    
+在上述例题中，由于每个物体只有 $2$ 种可能的状态（取与不取），正如二进制中的 $0$ 和 $1$，这类问题便被称为 “0-1 背包问题”。
 
 ## 0-1 背包
 
-例题中已知条件有第 i 个物体的体积 v[i]和价值 w[i], 背包总容量
+例题中已知条件有第 $i$ 个物品的重量 $w_{i}$，价值 $v_{i}$，以及背包的总容量 $W$。
 
-显而易见的是，可以计算总价值的，只有已经放入背包的物体，因此该题中对 "是否为最大值" 的判断是建立在 "已经放入背包之中" 的基础之上的
+设 DP 状态 $f_{i,W}$ 为在只能放前 $i$ 个物品的情况下，容量为 $W$ 的背包所能达到的最大总价值。
 
-已知对于一个容量为 v1，可以放置第 1 到第 i 件物体的背包，其最大总价值很明显等于容量为 v1 的背包，放有第 1 到第 (i-1) 件物体时的最大值（第 i 件物体不取时）或者是容量为 v1-v[i]的背包，放有第 1 到第 (i-1) 件物体时的最大值 + w[i](第i件物体取时)
+考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f_{i-1,W}$；当其放入背包时，背包的剩余容量会减小 $w_{i}$，背包中物品的总价值会增大 $v_{i}$，故这种情况的最大价值为 $f_{i-1,W-w_{i}}+v_{i}$。
 
-由此可以得出状态转移方程
+由此可以得出状态转移方程：
 
--   dp[v1][i]=max(dp[v1][i-1],dp[v1-v\[i\]][i-1]+w[i])
+$$f_{i,W}=\max(f_{i-1,W},f_{i-1,W-w_{i}}+v_{i})$$
 
-有了这样的思路，就可以顺利地写出代码了
+在程序实现的时候，由于对当前状态有影响的只有 $f_{i-1}$，故可以去掉第一维，直接用 $dp_{W}$ 来表示处理到当前物品 $i$ 时背包容量为 $W$ 的最大价值 $f_{i,W}$。
+
+还有一点需要注意的是，很容易写出这样的错误核心代码：
 
 ```cpp
-for (int i = 1; i <= v1; i++)
-  for (int l = 0; l <= v1 - i; l++) dp[l + i] = max(dp[l] + w[i], dp[l + i]);
+for (int i = 1; i <= W; i++)
+  for (int l = 0; l <= W - i; l++)
+    dp[l + w[i]] = max(dp[l] + v[i], dp[l + w[i]]);
+    // 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]],f[i - 1][l] + w[i]),f[i][l + w[i]]); 简化而来
 ```
 
-按照正确的思路，写出了这样的核心代码，然后就可以提交……
-
-错！
-
-让我们再回头看一下代码，i 表示当前判断的是第 i 个物体，l 则穷举体积，可是注意一个地方——l 是从 0 到 v1-v[i]
-
-这意味着什么呢？举个栗子，可能在体积为 (l) 处取物体 i 新的 dp 值存到体积为 (l+v[i]) 处，而在体积为 (l+v[i]) 处，物体 i 再次被取
+这段代码哪里错了呢？枚举顺序错了。
 
-所以，当以 0~v1-v[i]的顺序穷举时，物体实际上可能被加入多遍，这显然与题意不符
+仔细观察代码可以发现：对于当前处理的物品 $i$ 和当前状态 $f_{i,W}$，在 $W\geqslant w_{i}$ 时，$f_{i,W}$ 是会被 $f_{i,W-w_{i}}$ 所影响的。这就相当于物品 $i$ 可以多次被放入背包，与题意不符。（事实上，这正是完全背包问题的解法）
 
-因此为了避免多取，穷举顺序应为 v1-v[i]~0
+为了避免这种情况发生，我们可以改变枚举的顺序，从 $W$ 枚举到 $w_{i}$，这样就不会出现上述的错误，因为 $f_{i,W}$ 总是在 $f_{i,W-w_{i}}$ 前被更新。
 
 因此实际核心代码为
 
 ```cpp
-for (int i = 1; i <= v1; i++)
-  for (int l = v1 - i; l >= 0; l--) dp[l + i] = max(dp[l] + w[i], dp[l + i]);
+for (int i = 1; i <= W; i++)
+  for (int l = W - i; l >= 0; l--)
+    dp[l + i] = max(dp[l] + w[i], dp[l + i]);
+    // 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]],f[i - 1][l] + w[i]),f[i][l + w[i]]); 简化而来
 ```
 
-例题代码
-
-```cpp
-#include <bits/stdc++.h>
-using namespace std;
-const int maxn = 13010;
-int n, v, c[maxn], w[maxn], most[maxn];
-int main() {
-  cin >> n >> v;
-  for (int i = 1; i <= n; i++) {
-    cin >> c[i] >> w[i];
-  }
-  for (int i = 1; i <= n; i++)
-    for (int l = v; l >= c[i]; l--) {
-      if (most[l - c[i]] + w[i] > most[l]) most[l] = most[l - c[i]] + w[i];
+??? 例题代码
+
+    ```cpp
+    #include <iostream>
+    const int maxn = 13010;
+    int n, v, w[maxn], v[maxn], dp[maxn];
+    int main() {
+      std::cin >> n >> W;
+      for (int i = 1; i <= n; i++)
+        std::cin >> w[i] >> v[i];
+      for (int i = 1; i <= n; i++)
+        for (int l = W; l >= w[i]; l--)
+          if (dp[l - w[i]] + v[i] > dp[l])
+            dp[l] = dp[l - w[i]] + v[i];
+      std::cout << dp[W];
+      return 0;
     }
-  cout << most[v];
-  return 0;
-}
-```
-
-Ps. 事实上，由小到大穷举是另一种背包问题的解法，稍后会提到
+    ```
 
 ## 完全背包
 
-- 
2.11.0