首页 > 编程笔记 > C++笔记 阅读：140

多重背包问题详解（C++实现）

多重背包问题是背包问题的一种变体，允许每种物品有多个单位可以选择，但每种物品都有一个数量上限，即最多只能选取该物品的指定数量。

也就是说，多重背包和 0-1 背包、完全背包的区别是：
以下是多重背包问题的示例程序代码： 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;          // 定义常量 N，表示数组的最大长度
int a[N], b[N], t = 0, n, m, dp[N], v, w, s;
// 定义变量 a、b、t、n、m、dp、v、w、s

int main() {
    cin >> n >> m;              // 输入物品数量和背包容量
    while (n--) {               // 遍历每件物品
        cin >> v >> w >> s;     // 输入物品的价值、重量和数量
        while (s--) {           // 将多重背包拆成 0-1 背包
            a[++t] = v;         // 记录物品的价值
            b[t] = w;           // 记录物品的重量
        }
    }
    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]); // 更新 dp 数组，套用 0-1 背包问题的动态规划转移方程

    cout << dp[m] << endl;      // 输出最大总价值
    return 0;
}
运行结果为：

3 10
1 2 3
2 3 2
3 4 2
16

多重背包问题的上述动态规划解法由于需要对所有物品（数量为 k）进行逐一遍历，导致时间复杂度较高。在实际应用中，可以通过二进制优化来减少状态数量，从而提高算法效率。

二进制优化的实现代码如下： 
#include <bits/stdc++.h>
using namespace std;

const int N = 12010, M = 2010;
// 定义常量 N 和 M，分别表示物品总数量和背包容量
int n, m;
// 物品数量和背包容量
int v[N], w[N];
// 定义物品体积和价值
int f[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;                 // 剩余物品数量减少
            k *= 2;                 // 二进制拆分因子翻倍
        }
        // 处理剩余物品
        if (s > 0) {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;                            // 更新总组数为分组后的组别数量
    // 转换为 0-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;
}
运行结果为：

3 10
1 2 3
2 3 2
3 4 2
16

相关文章