混合背包问题是背包问题的另一种变体，结合了0/1背包、多重背包和完全背包的特点。在混合背包问题中，每种物品可以选择放入背包的次数是有限的，而且也可以选择放入的数量是无限的。 问题的描述如下： 给定一个背包容量为m，有n种物品，每种物品有重量v[i]、价值w[i]、以及数量s[i]。其中，s[i]表示第i种物品的数量限制。目标是选择物品放入背包，使得它们的总重量不超过背包容量，并且总价值最大。 解决混合背包问题的方法需要考虑每种物品的数量限制。可以将问题拆分为若干个子问题，对于每种物品分别处理。可以采用动态规划的方法，类似于多重背包问题，但需要考虑不同物品的数量限制。 一种常见的方法是将每种物品拆分成多个子物品，其中每个子物品对应放入背包的数量。然后，可以使用类似于多重背包问题的解法来处理这个扩展后的问题。 总体而言，解决混合背包问题需要综合考虑每种物品的多重性和数量限制，选择适当的方法进行求解。
这里由acwing中的题作为例题7. 混合背包问题 - AcWing题库
这里无非就是01背包、多重背包、完全背包混合起来罢了，根据是什么背包，分类讨论就好了，当s==-1的时候就是01背包，当s==0的时候就是完全背包，当s>0的时候就是多重背包，三个if判断便可以分类解决，对前面01背包、多重背包、完全背包不熟悉的可以看一下我之前写的博客，这里不再详细讲解。
01背包：初谈背包问题-CSDN博客
多重背包：细谈多重背包问题-CSDN博客
完全背包：浅谈完全背包问题-CSDN博客
代码语言：javascript复制#include<iostream>
using namespace std;
int v[1005],w[1005],s[1005];//s[i]表示物品特性，是01还是多重还是完全
int n,m;
int dp[10005],vis[10005];//vis[i]==1表示第i个物品是完全背包，==0表示01背包
int v1[10005],w1[10005];//最终转换成的01背包和完全背包
int main(){
int index=0;
cin>>n>>m;
for(int i=1;i<=n;i ){
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i ){
if(s[i]==0){//完全背包问题
vis[ index]=1;
v1[index]=v[i];
w1[index]=w[i];
continue;
}
if(s[i]==-1){//01背包问题
v1[ index]=v[i];
w1[index]=w[i];
continue;
}
//多重背包问题
for(int j=1;j<=s[i];j<<=1){
s[i]-=j;
v1[ index]=j*v[i];
w1[index]=j*w[i];
}
if(s[i]){
v1[ index]=s[i]*v[i];
w1[index]=s[i]*w[i];
s[i]=0;
}
}
for(int i=1;i<=index;i ){
if(vis[i]==1){//完全背包
for(int j=v1[i];j<=m;j ){
dp[j]=max(dp[j],dp[j-v1[i]] w1[i]);
}
}else{//01背包
for(int j=m;j>=v1[i];j--){
dp[j]=max(dp[j],dp[j-v1[i]] w1[i]);
}
}
}
cout<<dp[m]<<endl;
return 0;
}笔者水平有限，一些地方表达的可能不是很好，或者有错误地方，代码写的也不是很规范，望大家理解，希望对大家有帮助，下篇更新二维费用背包。
