概念：什么是01背包

01背包，顾名思义，每一个项不是 $0$ 就是 $1$ 的背包。显而易见，就是选和不选的背包。

那就是说，这是一个每个物品只有一个，且只能选货不选得出最大价值的背包问题

证明：怎么做01背包

先来看看这道题，显而易见有两种可能，一是贪心，二是 $D P$ 。那么是哪一种呢？不用想太多，我们可以感性理解。

假设你在买东西，对于一样的物品，你怎么选？肯定是选性价比高的啊！性价比就是性能和价格的比值，体现在这个题目中，他给我们造成的收益是性能，也就是购买这个物品的价值；我们选择它花费的代价是价格，也就是体积。

所以如果要贪心，一种方法就是按照性价比排序，所以说我们或许只需要出一个数据卡掉他，他就是DP题了。

cpp

70 3    // 背包体积 物品数量
// 物品体积 物品价值
60 600  // 性价比：10
20 180  // 性价比：9
50 430  // 性价比：8.6

按照贪心的方法，他选了 $60$ 就不可以再次选了，但是我们知道最优解是选 $20 + 50$ 。这也告诉我们这是一道 $D P$ 而非贪心。

推导：如何设计01背包

首先从最简单的开始。首先一个重要的变量是目前选的物品的体积，答案是所有选择的物品的价值，还有一个信息是选择的范围。

那么就可以依此写出 $D P$ 状态。

cpp

1 2	dp[i][j]; // 表示：前 i 个物品里选择出体积为 j 的最大价值

那么也很简单了，递推方程就是

d p [i] [j] = m a x (d p [i - 1] [j], d p [i - 1] [j - v [i]] + p [i]);

分别表示不选和选择当前的这个物品获得的价值。

那么现在最最初步的01背包代码也可以写出来了。

cpp

for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= V; j++) {
        dp[i][j] = dp[i - 1][j];
        if(j - a[i] >= 0){
            dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + b[i]);
        }
    }
}

优化：压缩空间

我们发现，只要我们买了一个新的物品（或者说多选择了一个但没买），那么以后的东西对于我们就没有用了，这就是 $D P$ 的无后效性。那么也就是说，我们就可以在我们 $\tt DP \ $ 状态上做手脚。

第一维是购买物品的范围，按照这个无后效性的说法，我们可以直接把它压掉。就像这个代码中， $d p [i] [j]$ 的初始值是直接从 $d p [i - 1] [j]$ 中拿下来。然后为了保证每一个物品只选一次，所以说每一个物品的状态更新时都得是没有更新过的数据，所以我们得倒着来，代码如下：

cpp

for(int i = 1; i <= n; i++) {
    for(int j = V; j >= 0; j--) {
        if(j - a[i] >= 0){
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
}