题解：金明的预算方案

• 题目
  • 题目描述
  • 输入格式
• 解析
  • 错误思路
  • 正解
• 代码

题目

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过n元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的n元。于是，他把每件物品规定了一个重要度，分为5等：用整数1～5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过n元的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1,j2,…,jk则所求的总和为： vj1 * wj1 + vj2 * wj2 + ? + vjk * wjk。
请你帮助金明设计一个满足要求的购物单。

输入格式

第一行有两个整数，分别表示总钱数n和希望购买的物品个数m。 第2到第(m+1)行，每行三个整数，第(i+1)行的整数 vi,pi，qi 分别表示第i件物品的价格、重要度以及它对应的的主件。如果qi=0，表示该物品本身是主件。 ####输出格式 输出一行一个整数表示答案。

解析

01背包不能瞎用

错误思路

我原本的思想是将主件不变，每个附件与主件的价值和代价合并然后算成一个物品，进行01背包；

for(int i = 1;i <= m; i++){
	    scanf("%d %d %d" ,&a[i].v,&a[i].p,&a[i].q);
	    if(a[i].q != 0){
		    a[i].v = a[i].v + a[a[i].q].v;
		    a[i].p = a[i].p + a[a[i].q].p;
	    }
    }
    for(int i = 1;i <= m; i++){
	    for(int j = N;j >= a[i].v; j--){
		    dp[j] = max(dp[j],dp[j - a[i].v] + a[i].v * a[i].p);
	    }
    }         

提交之后发现：0。。。
为什么呢？因为在将主件和附件合并的过程中，其实已经相当于购买一次主件了，此时如果再继续去买主件，就买重了，所以答案会偏大。（千万别信样例）

正解

这道题我们基于主件使用背包，对每一个主件都有如下情况：
1、不买
2、买主件
3、买主件和一个附件
4、买主件和两个附件
（在主件有两个附件的情况下）
所以我们只需要对此将状态转移方程进行分类讨论即可：

dp[j] = max(dp[j], dp[j - a[i].v] + a[i].p * a[i].v);
int t1 = vis[i][1], t2 = vis[i][2];
if(t1 && j >= v(i) + v(t1)) dp[j] = max(dp[j], dp[j - v(i) - v(t1)] + val(i) + val(t1));
if(t2 && j >= v(i) + v(t2)) dp[j] = max(dp[j], dp[j - v(i) - v(t2)] + val(i) + val(t2));
if(t1 && t2 && j >= v(i) + v(t1) + v(t2)) dp[j] = max(dp[j], dp[j - v(i) - v(t1) - v(t2)] + val(i) + val(t1) + val(t2));     

代码

#include
using namespace std;
const int N=60+5;
int money, n, ans = 0, dp[32005], vis[N][3];
struct thing {
    int v, p, q;
} a[N];
int v(int x) {
    return a[x].v;
}
int val(int x) {
    return a[x].v * a[x].p;
}
int main() {
    scanf("%d %d" ,&money,&n);
    for(int i = 1; i <= n; i++) {
	    scanf("%d %d %d" ,&a[i].v,&a[i].p,&a[i].q);
    }
    memset(dp, 128, sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i<=n; i++) if(a[i].q) vis[a[i].q][++vis[a[i].q][0]] = i;
    for(int i = 1; i <= n; i++) {
	    if(a[i].q == 0) {
		    for(int j = money; j >= a[i].v; j--) {
			    dp[j] = max(dp[j], dp[j - a[i].v] + a[i].p * a[i].v);
			    int t1 = vis[i][1], t2 = vis[i][2];
			    if(t1 && j >= v(i) + v(t1)) dp[j] = max(dp[j], dp[j - v(i) - v(t1)] + val(i) + val(t1));
			    if(t2 && j >= v(i) + v(t2)) dp[j] = max(dp[j], dp[j - v(i) - v(t2)] + val(i) + val(t2));
			    if(t1 && t2 && j >= v(i) + v(t1) + v(t2)) dp[j] = max(dp[j], dp[j - v(i) - v(t1) - v(t2)] + val(i) + val(t1) + val(t2));
			    ans = max(ans, dp[j]);
		    }
	    }
    }
    printf("%d\n",ans);
    return 0;
}