混合背包 朴素版（枚举选择次数）
2026-01-03 12:01:31
发布于：四川
3阅读
0回复
0点赞
四要素分析：
状态：dp[i][j] 表示前 i 种物品、容量 j 的最大价值（二维状态覆盖“物品种类”和“背包容量”）。
转移：对第 i 种物品，枚举选择次数 k（0≤k≤min(k[i], j/w[i])），则 dp[i][j] = max(dp[i][j], dp[i-1][j - kw[i]] + kv[i])（遍历所有合法选择次数，取最大价值）。
边界：dp[0][j] = 0（前0种物品，价值为0）、dp[i][0] = 0（容量为0，价值为0）。
答案：dp[n][m]（前 n 种物品、容量 m 的最大价值）。
void multiple_packsack(){//多重背包：朴素枚举选择次数
for(int i=1;i<=n;i++){//遍历物品种类
for(int j=0;j<=m;j++){//遍历背包容量
// 枚举第i种物品的选择次数k（不超过数量k[i]且不超过容量限制）
for(int l=0;l*w[i]<=j&&l<=k[i];l++){
dp[i][j]=max(dp[i][j],dp[i-1][j-l*w[i]]+l*v[i]);
}
}
}
cout<<dp[n][m]<<endl; // 答案
}
二进制优化版（拆分为01背包）：
四要素分析：
状态：dp2[j] 表示容量 j 的最大价值（压缩为一维，通过二进制拆分将“有限次选择”转为“01背包单次选择”）。
转移：
若 k[i]*w[i] ≥ m（物品数量足够多，等价于完全背包）：正向遍历 j = w[i] ~ m，dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i])；
若 k[i]*w[i] < m（物品数量有限，二进制拆分）：将 k[i] 拆分为 2^0, 2^1,..., 剩余值，每组视为“01背包的单件物品”，反向遍历 j = m ~ 组重量，dp2[j] = max(dp2[j], dp2[j - 组重量] + 组价值)。
边界：dp2[j] = 0（初始所有容量的价值为0）。
答案：dp2[m]（容量 m 的最大价值）。
void multiple_packsack_optimize(){//多重背包：二进制优化（核心版）
for(int i=1;i<=n;i++){//遍历物品种类
if(k[i]*w[i]>=m){//数量足够多，按完全背包处理（转移1）
for(int j=w[i];j<=m;j++){
dp2[j]=max(dp2[j],dp2[j-w[i]]+v[i]);
}
}
else{//数量有限，二进制拆分后按01背包处理（转移2）
int tk=k[i]; // 剩余未拆分的物品数量
int k1=1; // 拆分的组大小（2^0, 2^1, ...）
while(k1<=tk){
// 01背包：反向迭代处理当前组
for(int j=m;j>=k1*w[i];j--){
dp2[j]=max(dp2[j],dp2[j-k1*w[i]]+k1*v[i]);
}
tk-=k1; // 减去已拆分的数量
k1=k1<<1; // 组大小翻倍（2^0→2^1→...）
}
// 处理剩余不足一组的数量
if(tk){
for(int j=m;j>=tk*w[i];j--){
dp2[j]=max(dp2[j],dp2[j-tk*w[i]]+tk*v[i]);
}
}
}
}
cout<<dp2[m]<<endl; // 答案（容量m的最大价值）
}
这里空空如也
有帮助，赞一个