[背包] 背包问题算法模板(模板)

文章目录

0. 前言

背包问题是众多 dp 问题的母题，是一个很重要的知识点。该博文基于背包九讲总结，会将背包九讲内容及模板题全部总结一般，也是鉴于学习进度，目前仅总结了 01 背包及优化模型，完全背包，多重背包，分组背包。

初次系统学习背包问题，总结不够到位，往各位同学批评指正！十分感谢~

---

背包问题共性：

• n 个物品，一个容量为 v 的背包
• 每个物品两个属性，体积 vi，价值 wi
• 要求在这些物品中挑总体积不大于 v 的物品并使背包装入物品的总价值 w 最大。不一定需要装满背包

1. 01背包

特点：

• 每件物品最多只用一次

2. 01背包问题

思路：

• 状态表示：f[i][j] 从前 i 个物品中选择且总体积不大于 j 的最大价值
• 状态计算：
  • 将整个状态划分成两类：
  • 不选第 i 个物品：f[i][j] = f[i-1][j]
  • 选第 i 个物品：f[i][j] = f[i-1][j-v[i]]+w[i]
    • 当背包容量不够时，即，j<v[i] 时：f[i][j] = f[i-1][j]
  • 故状态转移方程为：f[i][j]=max(f[i-1][j], f[i-1][j-v[i]]+w[i])
• 状态初始化：
  • f[0][0~m] = 0 表示在选择 0 件物品时对于任何体积来讲，其最大价值均为 0

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

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

int main() {
    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 = 0; j <= m; ++j) {
            f[i][j] = f[i - 1][j];	// 不选第i件物品的情况一定存在
            if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

如上分析过程及代码即为最朴素的 01 背包问题的解决方案。

---

01 背包优化滚动数组优化

• 能发现，f[i][j] 的状态转移仅使用到了 f[i-1][...]，故可以采用滚动数组来做。即当前层的状态转移仅与上一层有关
• 当前层是 i & 1，上一层是 i-1 & 1

滚动数组优化代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

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

int main() {
    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 = 0; j <= m; ++j) {
            f[i & 1][j] = f[i - 1 & 1][j];
            if (j >= v[i]) f[i & 1][j] = max(f[i - 1 & 1][j], f[i - 1 & 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

---

01 背包一维终极优化版本：

其实，从状态转移方程 f[i][j]=max(f[i-1][j], f[i-1][j-v[i]]+w[i]) 能够知道第一维 f[i] 只用到了 f[i-1]，且第二维不论是 f[i-1][j] 还是 f[i-1][j-v[i]] 第二维总是小于等于 j 的。基于滚动数组的思想，我们完全可以将其改为一维数组来再度优化空间和代码：

• 基于最朴素二维数组版本，我们可以直接删掉第一维，则 f[N][N] 变为 f[N]，仅枚举体积
• 则朴素代码中的 f[i][j]=f[i-1][j] 变为 f[j]=f[j] 成为恒等式，则可以直接删除
• if 判断中 j >= v[i]，此时仅有一维，当 j < v[i] 时，这个判断条件是没有意义的。故我们可以直接让 j 从 v[i] 开始，就可以删掉 if 判断了
• 此时，如果直接删掉第一维，则变为： f[j]=max(f[j],f[j-v[i]]+w[i])，这个转移方程其实和之前是不等价的。可将其在一维含义下还原成两维的含义，对比在优化过程中是否改变了原意。
  • 首先第 i 层算的 f[i][j] = max(f[i][j],...)，第 i 层算的 f[j] 一定是 f[i][j]，但是由于一维中是 f[j-v[i]]，j-v[i] 一定是严格小于 j 的，且我们的 j 是从小到大进行枚举体积的，j-v[i] 会在 j 之前被计算，那么一维中的 f[j-v[i]] 实际上是第 i 层的 j-v[i]，其等价于 f[i][j-v[i]，而实际上应该是 f[i-1][j-v[i]]
  • 故我们可以改变 j 的循环顺序来解决这个问题，让 j 从 m 到 v[i] 进行枚举，即从大到小枚举体积，那么当我们更新体积 j 时，这个 j-v[i] 还没被更新过，那么它就存的是 i-1 层的 j-v[i] 这样就等价于之前的状态转移方程了
• 至此，我们就完成了 01 背包问题的终极写法

一维 01 背包终极写法代码：

 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

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

int main() {
    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] << endl;
    return 0;
}

2. 完全背包

特点：

• 每件物品可以使用无限次

3. 完全背包问题

思路：

• 状态表示：f[i][j] 从前 i 个物品中选择且总体积不大于 j 的最大价值
• 状态计算：
  • 将整个状态划分成 k 类：
  • 选第 i 个物品 0 次：f[i][j] = f[i-1][j]
  • 选第 i 个物品 1 次：f[i][j] = f[i-1][j-v[i]]+w[i]
  • 选第 i 个物品 2 次：f[i][j] = f[i-1][j-2*v[i]]+2*w[i]
  • 选第 i 个物品 k 次：f[i][j] = f[i-1][j-k*v[i]]+k*w[i]
  • 故状态转移方程为：f[i][j]=max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]))
• 状态初始化：
  • f[0][0~m] = 0 表示在选择 0 件物品时对于任何体积来讲，其最大价值均为 0

这个时间复杂度是相当高的，是 O ( n 3 ) O(n^3) O(n3)，当 n = 1000 n = 1000 n=1000 时，计算量达到 1 e 9 1e9 1e9，妥妥的超时。不过这也是朴素做法的基本思想。

朴素思想的超时代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

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

int main() {
    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 = 0; j <= m; ++j) {
            for (int k = 0; k * v[i] <= j; ++k) {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

---

完全背包问题终极优化：

简单展开状态转移方程：

f[i][j]    =max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w,...)
f[i][j-v]  =max(           f[i-1][j-v], f[i-1][j-2v]+w, f[i-1][j-3v]+2w, f[i-1][j-4v]+3w,...)
f[i][j-v]+w=max(           f[i-1][j-v]+w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w, f[i-1][j-4v]+4w,...)
故：
f[i][j]    =max(f[i-1][j], f[i][j-v]+w);

这是一个经典的优化，可以优化掉一维的状态，时间复杂度优化为 O ( n 2 ) O(n^2) O(n2)。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

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

int main() {
    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 = 0; j <= m; ++j) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

对比下完全背包与 01 背包的转移方程：

• 01 背包： f[i][j]=max(f[i-1][j], f[i-1][j-v]+w)
• 完全背包：f[i][j]=max(f[i-1][j], f[i][j-v]+w)

01 背包从 i-1 转移过来，完全背包从 i 转移过来，就这一点不同。

那么完全背包也完全可以优化成一维：

一维终极优化代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1005;

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

int main() {
    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;
}

这里的优化就不需要从大到小枚举 j 了，这里的 f[j-v[i]] 就是需要第 i 层的 j-v[i]，在当前 i 层，j-v[i] 一定是先于 j 被更新的，满足要求。

3. 多重背包

特点：

• 每件物品有独立的个数限制，不得超过最大数量限制

4. 多重背包问题 I

思路：

• 状态表示：f[i][j] 从前 i 个物品中选择且总体积不大于 j 的最大价值
• 状态计算：
  • 将整个状态划分成 s[i]+1 类：
  • 选第 i 个物品 0 次：f[i][j] = f[i-1][j]
  • 选第 i 个物品 1 次：f[i][j] = f[i-1][j-v[i]]+w[i]
  • 选第 i 个物品 2 次：f[i][j] = f[i-1][j-2*v[i]]+2*w[i]
  • 选第 i 个物品 s[i] 次：f[i][j] = f[i-1][j-s[i]*v[i]]+s[i]*w[i] 最终就是该物品数量的最大限制。十分类似于完全背包问题
  • 故状态转移方程为：f[i][j]=max(f[i][j], f[i-1][j-k*v[i]]+k*w[i])), k=0, 1, 2,...
• 状态初始化：
  • f[0][0~m] = 0 表示在选择 0 件物品时对于任何体积来讲，其最大价值均为 0

朴素版本的多重背包问题与朴素版本的完全背包问题思想一模一样，代码稍作改动即可。时间复杂度仍为 O ( n 3 ) O(n^3) O(n3)，这里的 n = 100 n=100 n=100，故计算次数为 1 e 6 1e6 1e6，还是可以的。

朴素思想的暴力代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 105;

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

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

---

5. 多重背包问题 II

仍为多重背包问题，但数据范围增大，仍采用 O ( n 3 ) O(n^3) O(n3) 暴力则将达到 1000 ∗ 2000 ∗ 2000 = 4 e 9 1000 * 2000 * 2000 = 4e9 1000∗2000∗2000=4e9 40 亿的计算量，超时。

考虑展开状态转移方程，以完全背包问题优化方式进行优化：

f[i][j]    =max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, ... ,f[i-1][j-sv]+sw)
f[i][j-v]  =max(           f[i-1][j-v],   f[i-1][j-2v]+w,  ... ,f[i-1][j-sv]+(s-1)w, f[i-1][j-(s-1)v]+sw)

乍一看还挺工整，f[i][j-v] 和 f[i][j] 后面一部分是比较相似的，但是其中 f[i][j-v] 多了 f[i-1][j-(s-1)v]+sw 这一项，即现在我们已知 f[i][j-v] 的最大值，需要求解 f[i][j-v] 展开项中除过 f[i-1][j-(s-1)v]+sw 的最大值。这个操作是无法实现的，取最大值操作是不支持减法的。这就相当于给定一堆数的最大值，让你求解其中部分数的最大值，这是无法直接求得的。所以，我们无法直接使用完全背包优化方式来优化多重背包问题。

---

在此有一种神奇且经典的优化方式，称为：二进制优化方式

• 假设某组物品有 1023 个，那么我们真的需要枚举 1023 次吗？
• 这里可以采用二进制倍增的思想，将 1023 个物品进行打包，然后拼凑出 1~1023 中的任意数量的物品
• 思想类比快速幂，将 O ( n ) O(n) O(n) 优化到 O ( l o g n ) O(logn) O(logn)
• 即，若第 i 个物品数量为 s 个，优化流程为：
  • 将 s 拆分成二进制下的打包物品，s[i] 个就会变成 log s[i] 个
  • 然后对打包出来的物品做一遍 01 背包就行了，每个打包物品只能选 1 次。因为这些打包物品可以拼凑出来所有的情况

那么原来的算法时间复杂度为 O ( n v s ) O(nvs) O(nvs)，现在为 O ( n v l o g s ) O(nvlogs) O(nvlogs)。成功优化， 1000 ∗ 2000 ∗ l o g 2000 = 2 e 7 1000*2000*log2000=2e7 1000∗2000∗log2000=2e7，刚好能过。

这就是多重背包问题的经典优化：二进制优化。

二进制优化思想代码：

#include <iostream>
#include <algorithm>

using namespace std;

// 一共1000个物品，每个物品最多2000件，2^11=2048 数组大小开1000*11=11000
const int N = 11005, M = 2005; 

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

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;                  // 从 1 开始打包
        while (k <= s) {            
            cnt ++;                 // 记录新打包物品编号，每次打包k个第i个物品
            v[cnt] = a * k;         // k个一组，体积变大k倍
            w[cnt] = b * k;         // k个一组，价值变大k倍
            s -= k;                 // i物品总个数一次性减少k个
            k *= 2;                 // 倍增
        }
        if (s > 0) {                // 补上剩下的物品
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    n = cnt;    // 更新现在有的物品总数，将其转化为01背包问题，每个物品独立且只能选1次
    
    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;
}

4. 分组背包

特点：

• 物品有 n 组，每组物品有若干个
• 每组物品最多只能选一件物品

9. 分组背包问题

完全背包问题：枚举第 i 件物品选几个
分组背包问题：枚举第 i 组物品选哪个

思路：

• 状态表示：f[i][j] 从前 i 个物品中选择且总体积不大于 j 的最大价值
• 状态计算：
  • 将整个状态划分成 s[i]+1 类：
  • 不选第 i 组物品：f[i][j] = f[i-1][j]
  • 选第 i 组物品的第一个物品：f[i][j] = f[i-1][j-v[1]]+w[1]
  • 选第 i 组物品的第二个物品：f[i][j] = f[i-1][j-v[2]]+w[2]
  • 选第 i 组物品的第 s[i] 个物品：f[i][j] = f[i-1][j-v[s[i]]+w[s[i]] 最终就是该物品数量的最大限制。十分类似于完全背包问题
  • 故状态转移方程为：f[i][j]=max(f[i][j], f[i-1][j-v[k]]+w[k])), k=0, 1, 2,...s[i]
• 状态初始化：
  • f[0][0~m] = 0 表示在选择 0 件物品时对于任何体积来讲，其最大价值均为 0

同理，分组背包问题也是可以从二维优化到一维的。其实只需要谨记一点：

• 当我们当前状态需要用上层状态进行转移时，就从大到小枚举体积
• 当我们当前状态需要用本层状态进行转移时，就从小到大枚举体积

这就直接扔上来一维版本了，二维都写了这么多遍了，抓住代码思想，代码实现都大同小异。

分组背包终极优化版本代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 105;

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

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