多重背包合集

AcWing 4. 多重背包問題 I O(n^3)

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
int f[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int v,w,s;
		cin>>v>>w>>s;
		for(int j=m;j>=0;j--)
		for(int k=1;k<=s && k*v<=j;k++)
		f[j]=max(f[j],f[j-k*v]+k*w);
		
		
	}
	cout<<f[m];
	return 0;
} 
           

AcWing 5. 多重背包問題 II 當N，M，K都是上千的話，我們需要優化(二進制優化)

多重背包---->01背包，第i個物品有s個，我們就把它拆成s份放到物品組中去，直接拆的話數量也是多，也會TLE

二進制的拆法：

0~7：1 2 4的選法，即log2(x)上取整

如果是0~10的話，不能直接用1 2 4 8，因為這樣可以枚舉到0~15的所有數，是以我們需要對最後一個數進行減操作

即 1 2 4 3 ，物品x份，直接變成log(x)份 這道題複雜度：1000 * 11 * 2000 = 2*10^7

#include<bits/stdc++.h>
using namespace std;
const int N = 2020; 
int n,m,f[N];
struct Goods
{
	int v,w;
};
int main()
{
	vector<Goods> goods;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int v,w,s;
		cin>>v>>w>>s;
		for(int k=1;k<=s;k*=2)
		{
			s-=k;
			goods.push_back({v*k,w*k});
		}
		if(s>0) goods.push_back({v*s,w*s});
	}
	
	for(auto good:goods)
		for(int j=m;j>=good.v;j--)
		   f[j]=max(f[j],f[j-good.v]+good.w);
	cout<<f[m];	   
	return 0;
}
           

AcWing 6. 多重背包問題 III

資料範圍

0<N≤10000<N≤1000

0<V≤200000<V≤20000

0<vi,wi,si≤20000

這個時候就需用單調隊列進行優化