洛谷P1064 金明的预算方案

我会带着你远行 2022-05-28 08:29 149阅读 0赞

## 题目描述 ##

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件 附件

电脑 打印机，扫描仪

书柜 图书

书桌 台灯，文具

工作椅 无

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

设第j件物品的价格为v\[j\]，重要度为w\[j\]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：

v\[j1\]\*w\[j1\]+v\[j2\]\*w\[j2\]+ …+v\[jk\]\*w\[jk\]。（其中\*为乘号）

请你帮助金明设计一个满足要求的购物单。

## 输入输出格式 ##

输入格式：

输入的第1行，为两个正整数，用一个空格隔开：

N m （其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数

v p q （其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）

输出格式：

输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

## 输入输出样例 ##

输入样例\#1： 复制

1000 5
    800 2 0
    400 5 1
    300 5 1
    400 3 0
    500 2 0

输出样例\#1： 复制

2200

## 说明 ##

NOIP 2006 提高组 第二题

我的错误思路，但我还是要记录下来。

这道题刚开始我也知道是个背包，但我的思路错了，没像题解那样分五种情况。我是每个物品看它是不是主件，如果是主件就01只买这个主件；如果是附件的话就看它的主件买没买，如果它的主件买了就01这个附件，如果它的主件没买就看单买主件和买主件和附件的这两种情况。

只得了10分，看来还真是个错误思路，唉。。。。为什么我就想不粗来，为什么啊为什么，很迷茫，看到的朋友可以安慰一下我吗？

#include<iostream>
    #include<string.h>
    using namespace std;
    
    struct node
    {
    	int v;
    	int p;
    	int q;
    	int value;
    	}woods[62];
    
    	bool flag[62];
    
    	int dp[32005];
    	int m;
    	int N;
    	int main()
    	{
    	freopen("1.txt", "r", stdin);
    	cin >> N >> m;
    	for (int i = 1; i <= m; i++)
    	{
    	cin >> woods[i].v >> woods[i].p >> woods[i].q;
    	woods[i].value = woods[i].p*woods[i].v;
    	}
    
    	for (int i = 1; i <= m; i++)
    	{
    	memset(flag,false,sizeof(flag));
    	for (int j = N; j >= woods[i].v; j--)
    	{
    	if (j>woods[i].v)
    	{
    	if (woods[i].q == 0)
    	{
    	int pt = dp[j - woods[i].v] + woods[i].value;
    	if (pt > dp[j])
    	{
    	dp[j] = pt;
    	flag[i] = true;
    	}
    	}
    	else
    	{
    	int mainthing = woods[i].q;
    	if (flag[mainthing])
    	{
    	int pt = dp[j - woods[i].v] + woods[i].value;
    	if (pt > dp[j])
    	{
    	dp[j] = pt;
    	//woods[i].flag = true;
    	}
    	}
    	else
    	{
    	if (j > woods[i].v + woods[mainthing].v)
    	{
    	int pt = dp[j - woods[i].v - woods[mainthing].v] + woods[i].value + woods[mainthing].value;
    	if (pt > dp[j])
    	{
    	dp[j] = pt;
    	flag[mainthing] = true;
    	}
    	}
    	else if (j > woods[mainthing].v)
    	{
    	int pt = dp[woods[mainthing].v] + woods[mainthing].value;
    	if (pt > dp[j])
    	{
    	dp[j] = pt;
    	flag[mainthing] = true;
    	}
    	}
    	}
    	}
    	}
    	}
    	}
    	cout << dp[N];
    	return 0;
    	}

正解：

参考题解：[https://www.luogu.org/blog/user20197/solution-p1064][https_www.luogu.org_blog_user20197_solution-p1064]

带有附件的背包问题，它属于01背包的变式。

这题还好，每一个物品最多只有两个附件，那么我们在对主件进行背包的时候，决策就不再是两个了，而是五个。

还记得01背包的决策是什么吗？

1.不选，然后去考虑下一个

2.选，背包容量减掉那个重量，总值加上那个价值。

这个题的决策是五个，分别是：

1.不选，然后去考虑下一个

2.选且只选这个主件

3.选这个主件，并且选附件1

4.选这个主件，并且选附件2

5.选这个主件，并且选附件1和附件2.

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    #define Maxn 32005
    
    int main_v[Maxn];
    int main_w[Maxn];
    
    int item_of_main_w[Maxn][3];
    int item_of_main_v[Maxn][3];
    
    int dp[Maxn];
    
    int N, m;
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> N >> m;
    	int v, p, q;
    	for (int i = 1; i <= m; i++)
    	{
    		cin >> v >> p >> q;
    		if (q == 0)
    		{
    			main_w[i] = v;
    			main_v[i] = v*p;
    		}
    		else
    		{
    			item_of_main_w[q][0]++;
    			item_of_main_w[q][item_of_main_w[q][0]] = v;
    			item_of_main_v[q][item_of_main_w[q][0]] = v*p;
    		}
    	}
    
    	for (int i = 1; i <= m; i++)
    	{
    		for (int j = N; main_w[i] && j >= main_w[i]; j--)
    		{
    			dp[j] = max(dp[j],dp[j-main_w[i]]+main_v[i]);
    
    			if (j >= main_w[i] + item_of_main_w[i][1])
    				dp[j] = max(dp[j], dp[j - main_w[i] - item_of_main_w[i][1]] + main_v[i] + item_of_main_v[i][1]);
    
    			if (j >= main_w[i] + item_of_main_w[i][2])
    				dp[j] = max(dp[j], dp[j - main_w[i] - item_of_main_w[i][2]] + main_v[i] + item_of_main_v[i][2]);
    			if (j >= main_w[i] + item_of_main_w[i][1] + item_of_main_w[i][2])
    				dp[j] = max(dp[j], dp[j - main_w[i] - item_of_main_w[i][1] - item_of_main_w[i][2]] + main_v[i]+ item_of_main_v[i][1] + item_of_main_v[i][2]);
    		}
    	}
    	cout<<dp[N];
    	return 0;
    }

[https_www.luogu.org_blog_user20197_solution-p1064]: https://www.luogu.org/blog/user20197/solution-p1064