【题解】金明的预算方案

原题传送门

题目描述

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

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

设第 \(j\) 件物品的价格为 \(v_j\)，重要度为\(w_j\)，共选中了 \(k\) 件物品，编号依次为 \(j_1,j_2,\dots,j_k\)，则所求的总和为：

\(v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}\)。

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

输入格式

第一行有两个整数，分别表示总钱数 \(n\) 和希望购买的物品个数 \(m\)。

第 \(2\) 到第 \((m + 1)\) 行，每行三个整数，第 \((i + 1)\) 行的整数 \(v_i\)，\(p_i\)，\(q_i\) 分别表示第 \(i\) 件物品的价格、重要度以及它对应的的主件。如果 \(q_i=0\)，表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

2200

说明/提示

数据规模与约定

对于全部的测试点，保证 \(1 \leq n \leq 3.2 \times 10^4\)，\(1 \leq m \leq 60\)，\(0 \leq v_i \leq 10^4\)，\(1 \leq p_i \leq 5\)，\(0 \leq q_i \leq m\)，答案不超过 \(2 \times 10^5\)。

NOIP 2006 提高组 第二题

思路分析

01 背包好题。

根据题意，如果要买归类为附件的物品，必须先买该附件所属的主件，对于每个主件及其附件，我们不难想到 \(5\) 种可能，分别是：

• 都不买
• 只买主件
• 买主件和附件 \(1\)
• 买主件和附件 \(2\)
• 买主件、附件 \(1\) 和附件 \(2\)

我们求出这 \(5\) 种可能所对应的价值（价格 \(\times\) 重要性），跑 01 背包即可。

变量声明

对于这道题，我们可以把题中声明的变量套在 01 背包上，总钱数 \(n\) 我们可以认为是背包的承重 \(m\) （个人习惯，下同），而 01 背包的物品数则就是主件的个数（包含主件的附件），物品的价格 \(v_i\) 就是放入背包所占的空间 \(w_i\)，物品的重要性 \(p_i\) 就是物品的价值 \(v_i\)。

预处理

对于这道题，01 背包模板的 \(w_i\) 和 \(v_i\) 数组，我们可以改成两个二维数组 \(W_{i,op}\)，\(V_{i,op}\)。

• 当 \(op=0\)，\(W_{i,op}\) 表示第 \(i\) 组物品主件所占背包的空间，\(V_{i,op}\) 表示第 \(i\) 组物品主件的价值。

• 当 \(op=1\)，\(W_{i,op}\) 表示第 \(i\) 组物品附件 \(1\) 所占背包的空间，\(V_{i,op}\) 表示第 \(i\) 组物品附件 \(1\) 的价值。

• 当 \(op=2\)，\(W_{i,op}\) 表示第 \(i\) 组物品附件 \(2\) 所占背包的空间，\(V_{i,op}\) 表示第 \(i\) 组物品附件 \(2\) 的价值。

for(int i=1;i<=n;i++){
	int v,p,q;
	cin>>v>>p>>q;
    if(q==0){
		W[i][0]=v;
		V[i][0]=p;
	}else if(W[q][1]==0){//没有附件1，即这个物品是附件1
		W[q][1]=v;
		V[q][1]=p;
	}else{//有附件1，即这个物品是附件2
		W[q][2]=v;
		V[q][2]=p;
	}
}

01 背包模板变形

（由于第一种情况都不买不产生任何价值，所以可以忽略不计。）

模板中，dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 的 w[i] 和 v[i] 在本题中分为几种情况，注意 \(v_i\) 还要乘 \(w_i\)，除此之外，由于物品的重量不定（如，主件和主件加附件 \(1\)，重量不同），所以 for(int j=m;j>=w[i];j--) 的 w[i] 要改为 0，并加上几个 if 语句判断，if 语句及动态转移方程详见代码。

for(int i=1;i<=n;i++){
	for(int j=m;j>=0;j--){
		if(j>=W[i][0]){
			dp[j]=max(dp[j],dp[j-W[i][0]]+W[i][0]*V[i][0]);
		}
		if(j>=W[i][0]+W[i][1]){
			dp[j]=max(dp[j],dp[j-W[i][0]-W[i][1]]+W[i][0]*V[i][0]+W[i][1]*V[i][1]);
		}
		if(j>=W[i][0]+W[i][2]){
			dp[j]=max(dp[j],dp[j-W[i][0]-W[i][2]]+W[i][0]*V[i][0]+W[i][2]*V[i][2]);
		}
		if(j>=W[i][0]+W[i][1]+W[i][2]){
			dp[j]=max(dp[j],dp[j-W[i][0]-W[i][1]-W[i][2]]+W[i][0]*V[i][0]+W[i][1]*V[i][1]+W[i][2]*V[i][2]);
		}
	}
}

于是乎，我们将几个代码放在一起，这道题就解决了，该题的时间复杂度是 \(O(nm)\)。

\(\texttt{code}\)

/*Written by smx*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
int W[65][3],V[65][3],dp[32005];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","W",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int v,p,q;
		cin>>v>>p>>q;
		if(q==0){
			W[i][0]=v;
			V[i][0]=p;
		}else if(W[q][1]==0){
			W[q][1]=v;
			V[q][1]=p;
		}else{
			W[q][2]=v;
			V[q][2]=p;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			if(j>=W[i][0]){
				dp[j]=max(dp[j],dp[j-W[i][0]]+W[i][0]*V[i][0]);
			}
			if(j>=W[i][0]+W[i][1]){
				dp[j]=max(dp[j],dp[j-W[i][0]-W[i][1]]+W[i][0]*V[i][0]+W[i][1]*V[i][1]);
			}
			if(j>=W[i][0]+W[i][2]){
				dp[j]=max(dp[j],dp[j-W[i][0]-W[i][2]]+W[i][0]*V[i][0]+W[i][2]*V[i][2]);
			}
			if(j>=W[i][0]+W[i][1]+W[i][2]){
				dp[j]=max(dp[j],dp[j-W[i][0]-W[i][1]-W[i][2]]+W[i][0]*V[i][0]+W[i][1]*V[i][1]+W[i][2]*V[i][2]);
			}
		}
	}
	cout<<dp[m];
	return 0;
}

该文章参考 Anguei的题解。