金明的预算方案（变形01背包）

淩亂°似流年 2022-09-29 11:59 109阅读 0赞

问题描述

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

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。  
　　设第j件物品的价格为v\[j\]，重要度为w\[j\]，共选中了k件物品，编号依次为j\_1，j\_2，……，j\_k，则所求的总和为：  
　　v\[j\_1\]\*w\[j\_1\]+v\[j\_2\]\*w\[j\_2\]+ …+v\[j\_k\]\*w\[j\_k\]。（其中\*为乘号）  
　　请你帮助金明设计一个满足要求的购物单。

输入格式

输入文件budget.in 的第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是所属主件的编号）

输出格式

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

样例输入

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

样例输出

2200

题解：这其实是一道变形的01背包。

情况无非是4种：

//只取主件，  
//取主件 + 附件一，  
//取主件 + 附件二，  
//取主件 + 附件一 + 附件二 。

然后就可以进行dp了。

dp\[ i \]\[ j \]表示买前 i类物品，用了j元。

具体看代码。

代码：

#include<bits/stdc++.h>
 using namespace std;
 //只取主件，
 //取主件 + 附件一，
 //取主件 + 附件二，
 //取主件 + 附件一 + 附件二 
 int dp[65][32000]; 
 //dp[i][j]表示买前 i类物品，用了j元， 
 int w[65][3],v[65][3];
 int main()
 {
 	int n,m; 
 	int cost,q,p;
 	cin>>n>>m;
 //	n/=10;
 	for(int i=1;i<=m;i++)
 	{
 		cin>>cost>>p>>q;
 	//	cost/=10;
 		if(q==0){
 			w[i][q]=cost;
 			v[i][q]=cost*p;
 		}
 		else if(w[q][1]==0){
 			w[q][1]=cost;
 			v[q][1]=cost*p;
 		}
 		else{
 			w[q][2]=cost;
 			v[q][2]=cost*p;
 		}
 	}	
 	for(int i=1;i<=m;i++)
 	{
 		for(int j=0;j<=n;j++)
 		{
 			dp[i][j]=dp[i-1][j];
 			if(j>=w[i][0])
 			{
 				dp[i][j]=max(dp[i][j],dp[i-1][j-w[i][0]]+v[i][0]);
 			}
 			if(j>=w[i][0]+w[i][1])
 			{
 				dp[i][j]=max(dp[i][j],dp[i-1][j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]);
 			}
 			if(j>=w[i][0]+w[i][2])
 			{
 				dp[i][j]=max(dp[i][j],dp[i-1][j-w[i][0]-w[i][2]]+v[i][0]+v[i][2]);
 			}
 			if(j>=w[i][0]+w[i][1]+w[i][2])
 			{
 				dp[i][j]=max(dp[i][j],dp[i-1][j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]);
 			}
 		}
 	}
 	//cout<<dp[m][n]*10<<endl;
 	cout<<dp[m][n]<<endl;
 	return 0;
 }