Fork me on GitHub

【题解】 P1064 金明的预算方案

发表于 | 分类于 |

~~（啊啊啊这个sd题目卡了我半天QAQ

我为什么可以这么傻啊）~~

题目大意这里就不放了qwq，相信大家也能看懂quq

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为55等：用整数1-51−5表示，第55等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

这个题目我们可以考虑用分组背包做，因为每一组最多只有两个附件，那么我们分组背包里面的策略数也就有5种：选主件，主件+附件1，主件+附件2，主件+附件1+附件2，我们可以在预处理的时候把这几个状态都枚举出来

此外，因为状态很少，所以预处理的时候也可以判断每一个背包里面是不是都有两个附件，没有的话直接退出或者加它那一个附件就好了

附件所获得的价值用c[i]表示，需要花费w[i]的体力，这样我们可以在找附件的时候直接把它加上主件就好了，因为每个策略是互斥的，所以我们不用在意会不会选主件+附件会多加一遍主件

分组背包的原理就不讲了，请参考背包九讲qwq（逃

下面放上代码（代码里面也有部分注释qwq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

int a[10001][6],f[100001],w[10001],c[10001],n,m,t;//不会链表QAQ，就只能用数组模拟存储
  
int main()
{
 	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++)
	{
		int k;
		scanf("%d%d%d",&w[i],&c[i],&k);
		c[i]*=w[i];//直接把价值乘上
		if(k!=0)//如果不是主件就加到它依附的主件序号后面
			a[k][++a[k][0]]=i;
		else //是主件就加一组以他的序号为头的背包（千万不要图省空间qwq
		{
			t+=i;
			a[i][++a[i][0]]=i;
		}
	}
	for(int i=1; i<=t; i++)
	{
		if(a[i][0]>2)//如果他有俩附件
		{
			a[i][0]++;m++;
			w[m]+=w[a[i][1]]+w[a[i][2]]+w[a[i][3]]; w[a[i][2]]+=w[a[i][1]]; w[a[i][3]]+=w[a[i][1]];
			c[m]+=c[a[i][1]]+c[a[i][2]]+c[a[i][3]]; c[a[i][2]]+=c[a[i][1]]; c[a[i][3]]+=c[a[i][1]];			
			a[i][a[i][0]]=m;
			continue;
		} 
		if(a[i][0]<2) continue; //咋一个附件都没有呢，跳过！qwq
		if(a[i][0]==2) //正好有一个附件
		{
			w[a[i][2]]+=w[a[i][1]];
			c[a[i][2]]+=c[a[i][1]];
			continue;
		}
	}

	for(int k=1; k<=t; k++) //标准的分组背包
		for(int j=n; j>=0; j--)
			for(int i=1; i<=a[k][0]; i++)
				if(j>=w[a[k][i]])//一定注意判断一下是否能装
					f[j]=max(f[j],f[j-w[a[k][i]]]+c[a[k][i]]);
	printf("%d",f[n]);
					
}
召唤蕾姆