混合背包
1.问题定义：
混合背包问题是经典背包问题的一个变种，其中物品的类型不单一，而是混合了以下三种类型：
01 背包物品：每种物品最多只能选一次。
完全背包物品：每种物品可以选择无限次。
多重背包物品：每种物品有指定的最大数量 s_i。
目标是在背包容量为 V 的情况下，选择物品放入背包，使得总价值最大。
2.问题形式化：
假设有 N 种物品和一个容量为 V 的背包。第 i 件物品的体积是 v_i，价值是 w_i，数量是 s_i：
如果 s_i = -1：表示这是 01 背包物品（只能选 0 或 1 次）
如果 s_i = 0：表示这是完全背包物品（可选无限次）
如果 s_i > 0：表示这是多重背包物品（最多选 s_i 次）
3.基本思路：
我们可以根据物品的类型，分别用不同的状态转移方法处理。
动态规划状态定义： 设 dp[j] 表示容量为 j 的背包能装的最大价值。
三种情况的处理：
01 背包（s[i] = -1） 状态转移：逆序枚举容量，防止重复选择 dp[j] = max(dp[j], dp[j - v[i]] + w[i])，其中 j 从 V 到 v[i]
完全背包（s[i] = 0） 状态转移：正序枚举容量，允许重复选择 dp[j] = max(dp[j], dp[j - v[i]] + w[i])，其中 j 从 v[i] 到 V
多重背包（s[i] > 0） 可以用二进制优化转化为 01 背包问题，然后按 01 背包处理（逆序枚举）
二进制优化：将数量 s_i 拆分成 1, 2, 4, ..., 2^k, c（其中 c = s_i - (2^{k+1} - 1) 且 c > 0），这样这些系数的组合可以表示 0 到 s_i 之间的任意数量。每个拆分后的物品视为一个独立的 01 背包物品。
4.算法步骤：
读入物品数据 (v[i], w[i], s[i])
对每个物品：
如果是 01 背包：直接按 01 背包处理（逆序容量循环）
如果是完全背包：直接按完全背包处理（正序容量循环）
如果是多重背包：先二进制拆分，再把拆分后的每个物品按 01 背包处理
输出 dp[V]
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000; // 最大物品数
const int MAXV = 1000; // 最大背包容量
struct Good {
int kind; // 0:01背包, 1:完全背包
int v, w;
};
Good goods[MAXN * 20]; // 存储所有物品（考虑二进制拆分）
int dp[MAXV + 5]; // DP数组
int goods_cnt = 0; // 物品计数器
int main() {
int N, V;
cin >> N >> V;
// 读入并预处理物品
for (int i = 0; i < N; i++) {
int v, w, s;
cin >> v >> w >> s;
if (s == -1) {
// 01背包物品
goods[goods_cnt].kind = 0;
goods[goods_cnt].v = v;
goods[goods_cnt].w = w;
goods_cnt++;
} else if (s == 0) {
// 完全背包物品
goods[goods_cnt].kind = 1;
goods[goods_cnt].v = v;
goods[goods_cnt].w = w;
goods_cnt++;
} else {
// 多重背包物品 - 二进制拆分
int k = 1;
while (k <= s) {
goods[goods_cnt].kind = 0;
goods[goods_cnt].v = v * k;
goods[goods_cnt].w = w * k;
goods_cnt++;
s -= k;
k *= 2;
}
if (s > 0) {
goods[goods_cnt].kind = 0;
goods[goods_cnt].v = v * s;
goods[goods_cnt].w = w * s;
goods_cnt++;
}
}
}
// 初始化DP数组
for (int j = 0; j <= V; j++) {
dp[j] = 0;
}
// DP过程
for (int i = 0; i < goods_cnt; i++) {
int kind = goods[i].kind;
int v = goods[i].v;
int w = goods[i].w;
if (kind == 0) {
// 01背包或拆分后的多重背包物品
for (int j = V; j >= v; j--) {
if (dp[j] < dp[j - v] + w) {
dp[j] = dp[j - v] + w;
}
}
} else {
// 完全背包物品
for (int j = v; j <= V; j++) {
if (dp[j] < dp[j - v] + w) {
dp[j] = dp[j - v] + w;
}
}
}
}
cout << dp[V] << endl;
return 0;
}代码说明：
数组定义：
goods数组：存储所有物品，包括原始物品和二进制拆分后的物品
dp数组：动态规划状态数组
物品预处理：
01背包和完全背包物品直接存入goods数组
多重背包物品通过二进制拆分，将每个拆分后的物品视为01背包物品存入
DP过程：
遍历所有物品
对于01背包类型，从大到小遍历容量（防止重复选择）
对于完全背包类型，从小到大遍历容量（允许重复选择）
二进制拆分原理：
将数量s拆分为1, 2, 4, ..., 2^k, c（剩余部分）
这些数的组合可以表示0到s之间的任意整数
例如：s=10，拆分为1,2,4,3
4.例题
【题目描述】
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
【输入描述】
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
【输出描述】
仅一行，一个数，表示最大总价值。
【样例输入】
4 5 1 2 -1 2 4 1 3 4 0 4 5 2
【样例输出】
8
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。