混合背包问题

理解了前面两种背包，那么第三种背包理解起来就毫不费力了！！！

首先我们可以把物品拆开，把相同的num[i]件物品看成价值跟重量相同的num[i]件不同的物品，那么！！是不是就转化成了一个规模稍微大一点的01背包了。

我们可以分为两种情况：

1）完全背包

用顺序处理及m>=j>=a[i]（j--）。

2）

把物品拆开，一件一件进行。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int m,n,f[10001]={0},w[10001],v[10001],p[10001];
int a[10001],b[10001],l,r;
void init();
void work();
void insert(int,int);
int main()
{
	init();
	work();
	return 0;
}
void init()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>p[i];
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		if(p[i]==0||p[i]>m/v[i])p[i]=m/v[i];
		for(int d=0;d<v[i];d++)
		{
			l=1;
			r=0;
			for(int j=0;j<=(m-d)/v[i];j++)
			{
				insert(j,f[j*v[i]+d]-j*w[i]);
				if(a[l]<j-p[i]) l++;
				f[j*v[i]+d]=b[l]+j*w[i];
			}
		}
	}
	cout<<f[m]<<endl;
}
void insert(int x,int y)
{
	while(l<=r && b[r]<=y) r--;
	r++;a[r]=x;b[r]=y;
}

最后

以上就是无私薯片为你收集整理的混合背包问题的全部内容，希望文章能够帮你解决混合背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。