跳转至

背包问题的分类

  1. 01背包
  2. 完全背包
  3. 多重背包（easy version）
  4. 多重背包（hard version）
  5. 分组背包

以上五种背包问题在Acwing基础课均有讲解，我们将部分题解摘录下来。

01背包

  1. 题目介绍

有N件物品和一个容量为V的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。

「0-1 背包」是较为简单的动态规划问题，也是其余背包问题的基础。动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 i个物品的做出决策，「0-1」正好代表不选与选两种决定。

版本1 二维背包

1. 状态定义：

  • f[i][j] 表示前 i 个物品，背包容量 j 下的最优解（最大价值）。

当前的状态依赖于之前的状态，可以理解为从初始状态 f[0][0] = 0 开始决策。有 N 件物品，则需要 N 次决策，每一次对第 i 件物品的决策，状态 f[i][j] 不断由之前的状态更新而来。

2. 背包容量不够情况（j < v[i]）： - 对应代码：f[i][j] = f[i - 1][j]。

3. 背包容量够，可以选与不选第 i 个物品： - 选：f[i][j] = f[i - 1][j - v[i]] + w[i]。 - 不选：f[i][j] = f[i - 1][j]。

决策取最大价值，因此以上两种情况取 max()。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN];  // 物品体积
int w[MAXN];  // 物品价值
int f[MAXN][MAXN]; // f[i][j], j 体积下前 i 个物品的最大价值

int main() 
{
  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 = 1; j <= m; j++)
    {
      // 当前背包容量装不进第 i 个物品，则价值等于前 i-1 个物品
      if(j < v[i]) 
        f[i][j] = f[i - 1][j];
      // 能装，需进行决策是否选择第 i 个物品
      else  
        f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
    }      

  // 输出结果
  cout << f[n][m] << endl;

  return 0;
}

2.2 版本2 一维

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。

为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

1. 状态定义： - f[j] 表示 N 件物品，背包容量为 j 下的最优解。

2. 注意枚举背包容量 j 必须从 m 开始。

3. 为什么一维情况下枚举背包容量需要逆序？ - 在二维情况下，状态 f[i][j] 是由上一轮 i - 1 的状态得来的，f[i][j] 与 f[i - 1][j] 是独立的。而优化到一维后，如果我们还是正序，则有 f[较小体积] 更新到 f[较大体积]，则有可能本应该用第 i-1 轮的状态却用的是第 i 轮的状态。

4. 为什么逆序是更优的选择？ - 例如，一维状态第 i 轮对体积为 3 的物品进行决策，则 f[7] 由 f[4] 更新而来，这里的 f[4] 正确应该是 f[i - 1][4]，但从小到大枚举 j 这里的 f[4] 在第 i 轮计算却变成了 f[i][4]。当逆序枚举背包容量 j 时，我们求 f[7] 同样由 f[4] 更新，但由于是逆序，这里的 f[4] 还没有在第 i 轮计算，所以此时实际计算的 f[4] 仍然是 f[i - 1][4]。

5. 状态转移方程为： - f[j] = max(f[j], f[j - v[i]] + w[i])。

6. 代码示例： 

for(int i = 1; i <= n; i++) 
  for(int j = m; j >= 0; j--) {
    if(j < v[i]) 
      f[j] = f[j];      // 优化后，该行自动成立，可省略。
    else  
      f[j] = max(f[j], f[j - v[i]] + w[i]);          // 优化后
  }

7. 优化后的循环终止条件：

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]);

8. 关于状态f[j]的补充说明： - 二维下的状态定义 f[i][j] 是前 i 件物品，背包容量 j 下的最大价值。一维下，少了前 i 件物品这个维度，我们的代码中决策到第 i 件物品（循环到第 i 轮），f[j] 就是前 i 轮已经决策的物品且背包容量 j 下的最大价值。因此当执行完循环结构后，由于已经决策了所有物品，f[j] 就是所有物品背包容量 j 下的最大价值。即一维 f[j] 等价于二维 f[n][j]。

版本3 优化输入

我们注意到在处理数据时，我们是一个物品一个物品，一个一个体积的枚举。

因此我们可以不必开两个数组记录体积和价值，而是边输入边处理。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;

int f[MAXN]; // 

int main() 
{
  int n, m; 
  cin >> n >> m;

  for(int i = 1; i <= n; i++) {
    int v, w;
    cin >> v >> w;   // 边输入边处理
    for(int j = m; j >= v; j--)
      f[j] = max(f[j], f[j - v] + w);
  }

  cout << f[m] << endl;

  return 0;
}

三、完全背包问题

问题重述：

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式：

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi, wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N, V ≤ 1000

0 < vi, wi ≤ 1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10

C++ 代码

#include<iostream>
using namespace std;

const int N = 1010;
int f[N];
int v[N], w[N];

int main() {
  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 = v[i]; j <= m; j++)
      f[j] = max(f[j], f[j - v[i]] + w[i]);

  cout << f[m] << endl;
  return 0;
}

优化思路：

我们注意到在处理数据时，我们是一个物品一个物品，一个一个体积的枚举。

因此我们可以不必开两个数组记录体积和价值，而是边输入边处理。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int f[MAXN];

int main() {
  int n, m;
  cin >> n >> m;

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

  cout << f[m] << endl;

  return 0;
}

四、多重背包问题

题目描述：

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式

第一行两个整数，N，V 用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi, wi, si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N, V ≤ 100

0 < vi, wi, si ≤ 100

样例

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例

10

分析

当 si=1 时，相当于 01 背包中的一件物品。当 si>1 时，相当于 01 背包中的多个一件物品，故我们可以死拆（把多重背包拆成 01 背包）。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int a[10005], b[10005], t = 0, n, m, dp[10005] = { }, w, v, s;

int main() {
  cin >> n >> m;

  while(n--) {
    cin >> v >> w >> s;
    while(s--) {
      a[++t] = v;
      b[t] = w;
    } // 死拆，把多重背包拆成 01 背包
  }

  for(int i = 1; i <= t; i++)
    for(int j = m; j >= a[i]; j--)
      dp[j] = max(dp[j - a[i]] + b[i], dp[j]); // 直接套 01 背包的板子

  cout << dp[m] << endl;
  return 0;
}

简化代码

#include <bits/stdc++.h>

using namespace std;

int dp[1005], n, t, v, w, s;

main() {
  cin >> n >> t;
  while(n--) {
    cin >> w >> v >> s;
    while(s--)
      for(int j = t; j >= w; j--)
        dp[j] = max(dp[j], dp[j - w] + v);
  }
  cout << dp[t];
}

五、多重背包问题（hard version）

二进制优化的多重背包问题

分析

首先确认三点：

  1. 我们知道转化成 01 背包的基本思路就是：判断每件物品是取了好还是不取好。
  2. 我们知道任意一个实数可以由二进制数来表示，也就是 20 * 2k 其中一项或几项的和。
  3. 多重背包问题就是每件物品取多少件可以获得最大价值。

  1. 如果直接遍历转化为 01 背包问题，每次都拿一个来问取了好还是不取好，那么根据数据范围，这样的时间复杂度是 O(n^3)，也就是 10^9，这样是毫无疑问会超时的。

  2. 假如 10 个取 7 个好，那么在实际的遍历过程中在第 7 个以后经过状态转移方程其实已经是选择“不取”好了。现在，用二进制思想将其分堆，分成 k+1 个分别有 2^k 个的堆，然后拿这一堆一堆去问，我是取了好呢，还是不取好呢，经过 dp 选择之后，结果和拿一个一个来问的结果是完全一样的，因为 dp 选择的是最优结果，而根据第二点任意一个实数都可以用二进制来表示，如果最终选出来 10 个取 7 个是最优的在分堆的选择过程中分成了 2^0=1, 2^1=2, 2^2=4, 10−7=3 这四堆，然后去问四次，也就是拿去走 dp 状态转移方程，走的结果是第一堆 1 个，取了比不取好，第二堆 2 个，取了比不取好，第三堆四个，取了比不取好，第四堆 8 个，取了还不如不取，最后依旧是取了 1+2+4=7 个。

  3. 如果仍然不是很能理解的话，取这样一个例子: 要求在一堆苹果选出 n 个苹果。我们传统的思维是一个一个地去选，选够 n 个苹果就停止。这样选择的次数就是 n 次。

  4. 二进制优化思维就是：现在给出一堆苹果和 10 个箱子，选出 n 个苹果。将这一堆苹果分别按照 1, 2, 4, 8, 16, ... 512 分到 10 个箱子里，那么由于任何一个数字 x ∈ [0, 1023]（第 11 个箱子才能取到 1024）都可以从这 10 个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10 次。

比如：

  • 如果要拿 1001 次苹果，传统就是要拿 1001 次；二进制的思维，就是拿 7 个箱子就行（分别是装有 512、256、128、64、32、8、1 个苹果的这 7 个箱子）,这样一来，1001 次操作就变成 7 次操作就行了。

这样利用二进制优化，时间复杂度就从 O(n^3) 降到 O(n^2 logS)，从 4∗10^9 降到了 2∗10^7。

#include<iostream>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N]; // 物品的体积和价值
int f[M];       // 体积 < M

int main() {
    cin >> n >> m;
    int cnt = 0; // 分组的组别
    for (int i = 1; i <= n; i++) {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while (k <= s) {
            cnt++;           // 组别先增加
            v[cnt] = a * k;   // 整体体积
            w[cnt] = b * k;   // 整体价值
            s -= k;           // s 要减小
            k *= 2;           // 组别里的个数增加
        }
        // 剩余的一组
        if (s > 0) {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt; // 枚举次数正式由个数变成组别数
    // 01背包一维优化
    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] << endl;

    return 0;
}

六、分组背包问题

多组物品背包问题

题目描述

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；

每组数据接下来有 Si 行，每行有两个整数 vij, wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N, V ≤ 100

0 < Si ≤ 100

0 < vij, wij ≤ 100

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例

8

解析

这道题和 01 背包差不多，对于每组 Si 个物品，有 Si+1 种选法：fj = max(fj, fj−v0+w0, fj−v1+w1, …, fj−vSi+wSi)

就是说可以不选（选 0 个），选 1 个，选 2 个…选 Si 个。所以，我们先循环枚举所有体积，再循环枚举所有选择，最后得出状态转移方程：fj = max(fj, fj−vk+wk），其中 k 是枚举所有选择中的循环变量。

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

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

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        for (int j = 1; j <= s[i]; j++) {
            scanf("%d%d", &v[i][j], &w[i][j]);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) { //枚举所有体积
            for (int k = 1; k <= s[i]; k++) { //枚举所有选择
                if (v[i][k] <= j) { //必须要满足，否则下面的下标减出来是负数
                    f[j] = max(f[j]/*不选*/, f[j - v[i][k]] + w[i][k]/*选*/);
                }
            }
        }
    }

    printf("%d", f[m]);

    return 0;
}

评论