题目描述
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
|
主件 |
附件 |
|
电脑 |
打印机，扫描仪 |
|
书柜 |
图书 |
|
书桌 |
台灯，文具 |
|
工作椅 |
无 |
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 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 ] 。（其中 * 为乘号）
请你帮助王强设计一个满足要求的购物单。
-----------------------------------------------------------------------------------------
输入描述:
输入的第 1 行，为两个正整数，用一个空格隔开：N m
从第 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
输出
2200
C++实现：
1 #include <stdio.h> 2 #include <math.h> 3 #include <string> 4 #include <cstdlib> 5 #include <map> 6 #include <stack> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <queue> 11 #include <iostream> 12 #include <sstream> 13 14 using namespace std; 15 16 vector<vector<int> > memo; 17 vector<int> flag; 18 19 int bestValue(const vector<int>& value, 20 const vector<int>& prioriry, 21 const vector<int>& q, 22 int index,int totalMoney) 23 { 24 if(index == 0 && value[0] > totalMoney) { 25 return 0; 26 } 27 if (index < 0 || totalMoney <= 0 ) return 0; 28 29 if (memo[index][totalMoney] != -1) return memo[index][totalMoney]; 30 31 int res = bestValue(value,prioriry,q,index-1,totalMoney); 32 int newValue = 0; 33 if (totalMoney >= value[index] && flag[index] == 0) 34 { 35 // 如果是主件 36 if (q[index] == 0) 37 { 38 newValue = value[index]*prioriry[index] + bestValue(value,prioriry,q,index-1,totalMoney-value[index]); 39 res = max(res, newValue); 40 } else 41 // 如果是附件 42 { 43 if(totalMoney >= (value[index] + value[q[index]-1])) { 44 flag[q[index]-1] = 1; 45 newValue = value[index]*prioriry[index]+value[q[index]-1]*prioriry[q[index]-1]+ 46 bestValue(value,prioriry,q,index-1,totalMoney-(value[index] + value[q[index]-1])); 47 flag[q[index]-1] = 0; 48 res = max(res, newValue); 49 } 50 } 51 } 52 memo[index][totalMoney] = res; 53 return res; 54 } 55 56 /** 57 * Entrance 58 * @return 59 */ 60 int main () 61 { 62 vector<int> value; 63 vector<int> prioriry; 64 vector<int> q; 65 66 int totalMoney,goodsCount; 67 while (cin >> totalMoney >> goodsCount) 68 { 69 value.clear(); 70 prioriry.clear(); 71 q.clear(); 72 73 int newValue; 74 int newPriority; 75 int newQ; 76 while (goodsCount > 0) { 77 cin >> newValue >> newPriority >> newQ; 78 value.push_back(newValue); 79 prioriry.push_back(newPriority); 80 q.push_back(newQ); 81 goodsCount--; 82 } 83 84 flag = vector<int>(value.size(),0); 85 memo = vector<vector<int> >(value.size(),vector<int>(totalMoney + 1,-1)); 86 cout << bestValue(value,prioriry,q,value.size()-1,totalMoney) << endl; 87 } 88 }