有依赖的01背包问题（ 金明的预算方案）

考虑到每个主件最多只有两个附件，因此我们可以通过转化，把原问题转化为01背包问题来解决，在用01背包之前我们需要对输入数据进行处理，把每一种物品归类，即：把每一个主件和它的附件看作一类物品。处理好之后，我们就可以使用01背包算法了。在取某件物品时，我们只需要从以下四种方案中取最大的那种方案：只取主件、取主件＋附件1、取主件＋附件2、既主件＋附件1＋附件2。很容易得到如下状态转移方程：

f[i,j]=max{f[i-1,j]，

f[i-1,j-a[i,0]]+a[i,0]*b[i,0]，

f[i-1,0]-a[i,1]]+a[i,0]+a[i,1]*b[i,1]，

f[i-1,2]]+a[i,2]*b[i,2]，

f[i-1,1]-a[i,1]+a[i,2]}

其中，f[i,j]表示用j元钱，买前i类物品，所得的最大值，a[i,0]表示第i类物品主件的价格，a[i,1]表示第i类物品第1个附件的价格，a[i,2]表示第i类物品第2个附件的价格，b[i,0],b[i,1],2]分别表示主件、第1个附件和第2个附件的重要度。

#include <iostream>
using namespace std;
int zf[65][3],w[65][3],v[65][3],d[65][3205];
int main()
{
	int n,m,c,p,q,i,j,t;
	cin>>n>>m;
	n/=10; //都是10的整数倍，因此可以节约空间和时间 
	for(i=1;i<=m;i++)
	{
		cin>>c>>p>>q;
		c/=10; //同上 
		if(q==0) {w[i][q]=c; v[i][q]=c*p;}
		else if(w[q][1]==0) {w[q][1]=c;v[q][1]=c*p;}
		else {w[q][2]=c;v[q][2]=c*p;}
	}
	for(i=1;i<=m;i++)
	for(j=0;j<=n;j++)
	{
		d[i][j]=d[i-1][j];
		if(j>=w[i][0]) {t=d[i-1][j-w[i][0]]+v[i][0];if(t>d[i][j]) d[i][j]=t;}
		if(j>=w[i][0]+w[i][1]) {t=d[i-1][j-w[i][0]-w[i][1]]+v[i][0]+v[i][1];if(t>d[i][j]) d[i][j]=t;}
		if(j>=w[i][0]+w[i][2]) {t=d[i-1][j-w[i][0]-w[i][2]]+v[i][0]+v[i][2];if(t>d[i][j]) d[i][j]=t;}
		if(j>=w[i][0]+w[i][1]+w[i][2]) {t=d[i-1][j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2];if(t>d[i][j]) d[i][j]=t;}
	}
	cout<<d[m][n]*10<<endl;
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!