本文最后更新于：2020年10月21日晚上

定义

一个背包，背包的容量为m。

n种物品，每个物品有两个属性，体积w[i]，价值v[i]

每个物品只有一个，也就是说每个物品只有拿和不拿两种状态。

求能够装入背包的最大价值或取最大价值时物品的集合。

01背包

用子问题定义状态

$f[i][j]$ 前i个物品在背包体积为j的情况下总价值的最大值

状态转移方程： $f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])$

后面几个背包问题都是这个问题的衍生，这个方程看不懂的话后面的就难搞了，所以重点解释一下。

每个物品只有选和不选两种状态。
无论选或者不选，这个物品的状态都是由前一个物品(i-1)的最大价值转移过来的。
- 如果不选物品i的话，那么物品i就不消耗背包容量，所以从f[i-1][j]转移过来。
- 如果要选物品i的话，那么物品i就需要消耗w[i]的体积，所以从f[i-1][j-w[i]]转移过来。由于选择了物品i，所以价值需要加上v[i]，即f[i-1][j-w[i]] + v[i]。
选择第3点提到的两种状态中较大的即为f[i][j]的最大价值

复杂度

i和j分别是物品种类和背包容量，显而易见时间空间复杂度都是$O(nm)$。

代码

#include <iostream>
using namespace std;
const int N = 1010;

int f[N][N];
int n, m, v[N], w[N];

int main(){
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) 
    scanf("%d%d", &w[i], &v[i]);
    
  for (int i = 1; i <= n; ++i)		//循环物品
    for (int j = 1; j <= m; ++j) {	//循环背包容量
      f[i][j] = f[i - 1][j];		//不选
      if (w[i] > j) continue;		//如果当前背包容量不足也不选
      f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);	//取最大价值
    }
    
  int res = 0;
  for (int i = 1; i <= m; ++i)		//答案一定在物品选取前n个时
    res = max(res, f[n][i]);
  cout << res << endl;
  return 0;
}

优化

- 当我们循环第i个物品时，只会从i-1个物品的最大价值转移过来。
- 当我们循环第i个物品容量为j时，只会和容量为j-w[i]的作比较，显然$j >= j-w[i]$。
所以只要我们倒着循环体积，就只需要一维数组就可以了。
此时的状态转移方程是： $f[j]=max(f[j],f[j-w[i]]+v[i])$

需要注意的是，二维的时候j从第一个开始循环，且先赋值f[i-1][j]到f[i][j]。是因为f[i][j]可能从f[i-1][j-w[i]]转移过来，而物品i-1的体积w[i-1]可能大于j-w[i]，所以一定要第一个开始而不是从w[i]开始循环，只有这样才可以将前面的最大价值转移到后面来。

但是在一维的情况下，小于w[i]的本身就是上一个物品的最大价值列表，所以不需要再转移一次。
```
for (int i = 1; i <= n; ++i)
  for (int j = m; j >= w[i]; --j)
	f[j] = max(f[j], f[j - w[i]] + v[i]);
```
当我们循环第i个物品的时候，只会用到这一个物品的价值和体积，而不会用到其他物品的，所以可以将输入和计算最大值放在一起。
```
for (int i = 0; i < n; ++i) {
  scanf("%d%d", &w, &v);
    
  for (int j = m; j >= w; --j) 
    f[j] = max(f[j], f[j - w] + v);
}
```
当f数组全部被初始化为0时，f[i][j]或f[j]表示的是前i个物品在背包容量为j时的最大价值。所以直接输出f[m]就是答案，我们将f数组作为全局变量初始化的，所以默认就是0。
```
#include <iostream>
using namespace std;
const int N = 1010;

int f[N];
int n, m, v, w;

int main(){
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &w, &v);
    
    for (int j = m; j >= w; --j) 
      f[j] = max(f[j], f[j - w] + v);
  }
  
  cout << f[m] << endl;
  return 0;
}
```
- 当问题是背包容量是多少时能恰好装满背包且背包价值最大的话，就需要将f[0][0]初始化为0，而其他的都初始化为负无穷。
  再看状态转移方程f[j-w[i]] + v[i]，所有选择了物品的状态都是从上一个物品的最大价值加上v[i]而来，当初始化了负无穷时有，$j-w[i]==0$时能选择要选择这个物品，此时f[j-w[i]] + v[i]的值是0 + v[i]，否则是一个负值，所以j只能是物品体积的倍数时才能被选择。

完全背包

完全背包是在01背包的基础上将物品只有选和不选的限制改为了每种物品都可以选择无限多个。

令k为每件物品取到的个数，可以直接在01背包的基础上得出完全背包的一个状态转移方程：

$f[i][j]=max(f[i-1][j-kw[i]]+kv[i])$

直接使用这个状态转移方程需要在01背包的基础上加一层循环来枚举物品的个数，类似的代码参考后面的多重背包II。

回顾前面优化过的01背包，我们使用的是从后往前的方式，这是因为j-w[i]一定实在j的前面，所以取到的其实是f[i-1][j-w[i]]，所以f[j-w[i]]+v[i]的意思就是在f[i-1][j-w[i]]已经取到最优值的情况之上再取一个i所得到的价值。

由此，我们从前往后遍历，那么f[j-w[i]]+v[i]的意思就是在f[i][j-w[i]]已经取到最优值得情况之上再去一个i所得到的价值。而f[i][j-w[i]]已经取到了j-w[i]/w[i]个i物品。

代码

#include <iostream>
using namespace std;
const int N = 1010;

int f[N];
int n, m, v, w;

int main(){
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &w, &v);
      
    for (int j = w; j <= m; ++j)
      f[j] = max(f[j], f[j - w] + v);
  }
  cout << f[m] << endl;
  return 0;
}

多重背包I

多重背包是在完全背包的基础上将每个物品可以选择无限多次改为了每种物品只能选择s[i]次。

在完全背包里面提到了可以用第三重循环来枚举k的取值，这里就以这样的方式来写代码。

代码

#include <iostream>
using namespace std;
const int N = 110;

int f[N];
int n, m, s, w, v;

int main(){
  cin >> n >> m;
  for (int i = 0; i < n; ++i){
    scanf("%d%d%d", &w, &v, &s);
    
    for (int j = m; j >= w; --j)
      for (int k = 1; k <= s && k * w <= j; ++k)
        f[j] = max(f[j], f[j - k * w] + k * v);
  }
  cout << f[m] << endl;
  return 0;
}

这是最暴力的写法，它有两种优化方法，会在下面提到。

多重背包II

多重背包的二进制优化。

上一种方法的时间复杂度显而易见是$O(nms)$，现在当n m s取值都是最大1000时，那么就是$10^9$，c/c++在1秒内最多能做$10^7-10^8$次操作，在这种数据量下还是用上面那种方法必然TLE。

回顾上一种方法，在第三重循环是在枚举物品的个数s，这里可以考虑将每种物品有s个转换为有s个一样的物品。这样的话就变成了01背包问题，但是n的取值就变到了$10^6$，时间复杂度就是$O(nm)$，依然会到$10^9$。

再回过头来，现在n种物品当中有许多都是相同的物品，这样的话就可以通过二进制的每一位数的数值来代替物品的个数，举个例子：15以内的每一个数可以通过·{1, 2, 4, 8}中的数组合表示，当总的个数不是2^k-1时，最后一个数取总数减去前几个输的和，举个例子13以内的通过{1, 2, 4, 6}来表示，如此一来，时间复杂度就是$O(nmlog(s))$，是小于$10^8$的。

代码

#include <iostream>
using namespace std;
const int N = 1e5;

int f[N];
int n, m, v, w, s;
int k, vv[N], ww[N], cnt;

int main(){
  cin >> n >> m;
  for (int i = 0; i < n; ++i){
    scanf("%d%d%d", &w, &v, &s);
    for (k = 1; k <= s; k <<= 1){	//取2^x次方
      s -= k;
      ww[cnt] = k * w;				//体积
      vv[cnt++] = k * v;			//价值
    }
    if (s) {
      ww[cnt] = s * w;
      vv[cnt++] = s * v;
    }
  }
  
  //01背包模板
  for (int i = 0; i < cnt; ++i) 
    for (int j = m; j >= ww[i]; --j)
      f[j] = max(f[j], f[j - ww[i]] + vv[i]);
  
  cout << f[m] << endl;
  return 0;
}