题目

有$N$件物品和一个容量为$V$的背包。第i件物品的费用是$c[i]$，价值是$w[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即$f[i][v]$表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：$f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}$。

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前$i-1$件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前$i-1$件物品放入剩下的容量为$v-c[i]$的背包中”，此时能获得的最大价值就是$f[i-1][v-c[i]]$再加上通过放入第i件物品获得的价值$w[i]$。

注意$f[i][v]$有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是$f[N][V]$，而是$f[N][0..V]$的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项$f[i][v-1]$，这样就可以保证$f[N][V]$就是最后的答案。至于为什么这样就可以，由你自己来体会了。

优化空间复杂度

以上方法的时间和空间复杂度均为$O(N*V)$，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到$O(V)$。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环$i=1..N$，每次算出来二维数组$f[i][0..V]$的所有值。那么，如果只用一个数组$f[0..V]$，能不能保证第$i$次循环结束后$f[v]$中表示的就是我们定义的状态$f[i][v]$呢？$f[i][v]$是由$f[i-1][v]$和$f[i-1] [v-c[i]]$两个子问题递推而来，能否保证在推$f[i][v]$时（也即在第i次主循环中推$f[v]$时）能够得到$f[i-1][v]$和$f[i-1][v-c[i]]$的值呢？事实上，这要求在每次主循环中我们以$v=V..0$的顺序推$f[v]$，这样才能保证推$f[v]$时$f[v-c[i]]$保存的是状态$f[i -1][v-c[i]]$的值。伪代码如下：

for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的$f[v]=max{f[v],f[v-c[i]]}$一句恰就相当于我们的转移方程$f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}$，因为现在的$f[v-c[i]]$就相当于原来的$f[i-1][v-c[i]]$。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了$f[i][v]$由$f[i][v-c[i]]$推知，与本题意不符，但它却是另一个重要的背包问题（完全背包）最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

总结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

代码：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
using namespace std;
const int N=1000;
int v[N+50],w[N+50];
int f[N+50];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}