有 n
种物品要放到一个袋子里，袋子的总容量为 m
。
物品一共有 3
类，第 i
种物品属于第 ai
类，它的体积为 vi
，把它放进袋子里会获得 wi
的收益。
如果它属于第 1
类物品，每种只能用一次。
如果它属于第 2
类物品，每种可以用无限多次。
如果它属于第 3
类物品，每种可以用 li
次。
问如何选择物品，使得在物品的总体积不超过 m
的情况下，获得最大的收益？请求出最大收益。
输入格式
第一行两个整数 n,m
。
接下来 n
行，每行三到四个整数 ai,vi,wi
或 ai,vi,wi,li
。
输出格式
一个整数，表示答案。
样例输入
5 10
1 6 5
3 3 4 2
1 5 2
3 3 5 2
2 3 2
样例输出
14
数据规模
对于所有数据，保证 1≤n,m,vi,wi,li≤1000,1≤ai≤3
。
混合背包
01背包和完全背包都可以化为多重背包
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int v[N],w[N],dp[N];
int cnt;
void bina(int vi,int wi,int s)
{
int t=1;
while(t<=s)
{
v[++cnt]=vi*t;
w[cnt]=wi*t;
s-=t;
t<<=1;
}
if(s) v[++cnt]=vi*s,w[cnt]=wi*s;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
int ai,vi,wi,s;
cin>>ai;
if(ai==1) {cin>>vi>>wi;s=1;}
else if(ai==2) {cin>>vi>>wi;s=m/vi;}
else {cin>>vi>>wi>>s;}
bina(vi,wi,s);
}
for(int i=1;i<=cnt;++i)
for(int j=m;j>=v[i];--j)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
cout<<dp[m]<<'\n';
}