90分蒟蒻求助
查看原帖
90分蒟蒻求助
112927
主编稻草一号楼主2021/10/19 20:14

麻了,实在不知道错在哪里了QAQ

#include<bits/stdc++.h>
using namespace std;
int f[61][32005],v[61][10],w[61][10],head[61],head2[61];//v:价格  w:重要度 head:记录元素数 head2:记录第i个物品在第几组
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=m;i++)
	{
		int vv,bb,ww;
		scanf("%d%d%d",&vv,&ww,&bb);
		if(bb==0)
		{
			head[0]++;
			head2[i]=head[0];
			v[head[0]][0]=vv;
			w[head[0]][0]=ww;
		}
		else
		{
			head[bb]++;
			head2[i]=head2[bb];
			v[head2[bb]][head[bb]]=vv;
			w[head2[bb]][head[bb]]=ww;
		}
	}//head[0]是用来分组的,其余是用来标每组元素个数的
	for(register int i=1;i<=head[0];i++)
	{
		int v0=v[i][0],v1=v[i][1],v2=v[i][2],w0=w[i][0],w1=w[i][1],w2=w[i][2];//最多共有5种情况:不取,取主,取主副1,取主副2,全取
		for(register int j=n;j>=v0;j--)
		{
			if(f[i-1][j-v0]+v0*w0>f[i][j]&&j-v0>=0)
			    f[i][j]=max(f[i-1][j-v0]+v0*w0,f[i-1][j]);
			if(f[i-1][j-v0-v1]+v0*w0+v1*w1>f[i][j]&&j-v0-v1>=0)
			    f[i][j]=max(f[i-1][j-v0-v1]+v0*w0+v1*w1,f[i-1][j]);
			if(f[i-1][j-v0-v2]+v0*w0+v2*w2>f[i][j]&&j-v0-v2>=0)
			    f[i][j]=max(f[i-1][j-v0-v2]+v0*w0+v2*w2,f[i-1][j]);
			if(f[i-1][j-v0-v1-v2]+v0*w0+v1*w1+v2*w2>f[i][j]&&j-v0-v1-v2>=0)
			    f[i][j]=max(f[i-1][j-v0-v1-v2]+v0*w0+v1*w1+v2*w2,f[i-1][j]);			
		}
	}
	printf("%d",f[head[0]][n]);
	return 0;
}
2021/10/19 20:14
加载中...