多重背包问题
一、问题定义
二、与其他背包问题的区别
三、朴素解法
直接遍历每种物品的所有可能选取数量（从 0 到最大限制数），通过动态规划更新最大价值。虽然时间复杂度较高（适合物品数量限制较小的场景），但逻辑简单易懂。
【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
// 多重背包问题（朴素解法）
// 参数：
// - weight：物品重量数组
// - value：物品价值数组
// - count：物品数量限制数组
// - n：物品种类数
// - W：背包最大承重
int boundedKnapsackNaive(int weight[], int value[], int count[], int n, int W) {
// dp[j]：承重为j时的最大价值
int dp[1001] = {0}; // 假设背包最大承重不超过1000
// 遍历每种物品
for (int i = 0; i < n; i++) {
// 逆向遍历承重（避免同一物品被重复选取多次，类似0-1背包的遍历逻辑）
for (int j = W; j >= weight[i]; j--) {
// 遍历当前物品的所有可能选取数量（k=0到最大可能数量）
// 最大可能数量：min(count[i], j / weight[i])（不超过数量限制，且不超重）
for (int k = 1; k <= count[i] && k * weight[i] <= j; k++) {
// 更新dp[j]：选取k个当前物品的最大价值
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
}
}
}
return dp[W];
}
int main() {
// 示例：3种物品，背包最大承重为10
int weight[] = {2, 3, 4}; // 物品重量
int value[] = {3, 5, 6}; // 物品价值
int count[] = {2, 2, 1}; // 物品数量限制（最多选2、2、1次）
int n = 3; // 物品种类数
int W = 10; // 背包最大承重
int maxVal = boundedKnapsackNaive(weight, value, count, n, W);
cout << "多重背包（朴素解法）的最大价值为：" << maxVal << endl; // 输出：16
return 0;
}1. 核心逻辑
2.示例解析
3. 时间复杂度
四、动态规划解法（二进制优化）
1. 二进制拆分原理
2. 算法步骤
3. 参考代码
#include <iostream>
#include <algorithm>
using namespace std;
// 最大虚拟物品数量（根据实际场景调整，确保足够存储拆分后的物品）
#define MAX_VIRTUAL_ITEMS 1000
// 多重背包问题（二进制优化，不使用vector）
// 参数：
// - weight：物品重量数组
// - value：物品价值数组
// - count：物品数量限制数组
// - n：物品种类数
// - W：背包最大承重
int boundedKnapsack(int weight[], int value[], int count[], int n, int W) {
// 步骤1：二进制拆分，生成虚拟物品（用普通数组存储）
int new_weight[MAX_VIRTUAL_ITEMS]; // 拆分后的虚拟物品重量
int new_value[MAX_VIRTUAL_ITEMS]; // 拆分后的虚拟物品价值
int virtual_count = 0; // 虚拟物品的总数量
for (int i = 0; i < n; i++) {
int cnt = count[i]; // 当前物品的数量限制
// 二进制拆分：2^0, 2^1, ..., 2^k（直到剩余数量为0）
for (int k = 1; cnt > 0; k *= 2) {
int take = min(k, cnt); // 本次拆分的数量（不超过剩余数量）
// 存储虚拟物品（重量和价值为原物品的take倍）
new_weight[virtual_count] = weight[i] * take;
new_value[virtual_count] = value[i] * take;
virtual_count++; // 虚拟物品数量+1
cnt -= take; // 剩余数量减少
}
}
// 步骤2：用0-1背包解法处理虚拟物品（逆向遍历承重）
int dp[1001] = {0}; // dp[j]：承重为j时的最大价值（假设W<=1000）
for (int i = 0; i < virtual_count; i++) {
// 逆向遍历，防止同一虚拟物品被多次选取（0-1背包特性）
for (int j = W; j >= new_weight[i]; j--) {
dp[j] = max(dp[j], dp[j - new_weight[i]] + new_value[i]);
}
}
return dp[W];
}
int main() {
// 示例：3种物品，背包最大承重为10
int weight[] = {2, 3, 4}; // 物品重量
int value[] = {3, 5, 6}; // 物品价值
int count[] = {2, 2, 1}; // 物品数量限制（最多选2、2、1次）
int n = 3; // 物品种类数
int W = 10; // 背包最大承重
int maxVal = boundedKnapsack(weight, value, count, n, W);
cout << "多重背包的最大价值为：" << maxVal << endl; // 输出：14
return 0;
}4. 示例
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
