混合背包
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