代码源：混合背包

ruoye123456 / 2023-09-05 / 原文

有 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';
}