混合背包问题

题目来源：7. 混合背包问题 - AcWing题库

题目

有?N种物品和一个容量是?V?的背包。

物品一共有三类：

• 第一类物品只能用1次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用?si?次（多重背包）；

每种体积是?vi，价值是?wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有?N行，每行三个整数?vi,wi,si，用空格隔开，分别表示第?i?种物品的体积、价值和数量。

• si=?1=?1?表示第?i?种物品只能用1次；
• si=0=0?表示第?i 种物品可以用无限次；
• si>0>0?表示第?i?种物品可以使用?si?次；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000
?1≤si≤1000

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

8

?题目解析：

可以把问题分成两类：0-1背包问题（见博客：01背包问题-CSDN博客），完全背包问题求解（见博客：完全背包问题-CSDN博客），对于多重背包问题，可以用二进制优化方法（博客：多重背包问题 II-CSDN博客）变成完全背包问题。

上代码：

#include<iostream> 
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
const int N=1010;
int n,m;
int f[N];

struct Thing{
	int tp;
	int v,w;
};

vector<Thing> things;

int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		int v,w,s;
		cin>>v>>w>>s;
		if(s<0)things.push_back({-1,v,w}) ;//0-1背包问题 
		else if(s==0)things.push_back({0,v,w});//完全背包问题 
		else
		{
			for(int k=1;k<=s;k*=2)//多重背包问题 
			{
				s-=k;
				things.push_back({-1,v*k,w*k});//转换成0-1背包问题 
			}
			if(s>0)things.push_back({-1,v*s,w*s});
		}
	}
	for(int x=0;x<things.size();x++) 
	{
		if(things[x].tp<0)//0-1背包的处理 
		{
			for(int i=m;i>=things[x].v;i--)
			{
				f[i]=max(f[i],f[i-things[x].v]+things[x].w);//从大到小遍历 
			}
		}
		else//完全背包的处理 
		{
			for(int i=things[x].v;i<=m;i++)
			{
				f[i]=max(f[i],f[i-things[x].v]+things[x].w);//从小到大遍历 
			}
		}
	}
	cout<<f[m];
	return 0;
}