动态规划 专题。

洛谷 P1064 金明的预算方案

题目描述

输入输出格式

说明

NOIP 2006 提高组 第二题

时空限制

  • 时间：1000ms
  • 空间：128MB

思路

这是 带附件的背包问题 ，我也是第一次接触，看了很久别人的题解，终于找到一个看懂了的题解。首先用一个结构体 good 记录物品的属性， good[i].v 表示物品 i 价格，good[i].w 表示物品 i 重要度。

然后，因为题目意思是至多带两个附件，于是在进行递推公式前，需要进行整理。用一个 flag 数组表示当前物品是否访问过。

1. z=0：表示该物品是主件，价格和总价值存入 good[i][0] 结构体
2. z!=0：
		flag[z]=0：表示当前物品没有访问过，存入 good[z][1] 结构体，表示附件一，同时将 flag[z] 置为 1
    	flag[z]!=0：表示当前物品已经访问过，存入 good[z][2] 结构体，表示附件二

下面就可以写出递推公式了。

1. j >= good[i][0].v 即只选主件：
	dp[j] = max(dp[j], dp[j-good[i][0].v]+good[i][0].w);  //不选当前件，选择当前件所以要花费当前物品的费用，再加上总价值 
2. j >= good[i][0].v+good[i][1].v 即选主件+附件1：
	dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v] + good[i][0].w+good[i][1].w); 
3. j >= good[i][0].v+good[i][2].v) 即选主件+附件2：
	dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][2].v] + good[i][0].w+good[i][2].w);
4. j >= good[i][0].v+good[i][1].v+good[i][2].v) 即都选：
	dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v-good[i][2].v] + good[i][0].w+good[i][1].w+good[i][2].w);
代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <math.h>
using namespace std;
int n,m;
struct goods{
	int v,w;
}good[100][3];  //0为主件、1为附件1、2为附件2 
int flag[100],dp[1000000];

int main(){
	memset(flag,0,sizeof(flag));
	scanf("%d%d",&n, &m);
	for(int i = 1; i <= m; ++i){  //从1开始 
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(z == 0){  //表示是主件 
			good[i][0].v = x;
			good[i][0].w = x*y;
		}
		else{  //是附件 
			if(flag[z] == 0){
				good[z][1].v = x;  //注意：第一维下标是z，这个错找了半个小时。 
				good[z][1].w = x*y;
				flag[z] = 1;  //表示是否访问过 
			}
			else{
				good[z][2].v = x;
				good[z][2].w = x*y;
				//flag[z] = 1; 
			}
		}
	}
	for(int i = 1; i <= m; ++i){  //i <= 可选的物品种类，从1开始 
		for(int j = n; j >= 0; --j){  //j = 总钱数 
			if(j >= good[i][0].v){  //只选主件 
				dp[j] = max(dp[j], dp[j-good[i][0].v]+good[i][0].w);  //不选当前件，选择当前件所以要花费当前物品的费用，再加上总价值 
			}
			if(j >= good[i][0].v+good[i][1].v){  //选主件+附件1 
				dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v] + 
				good[i][0].w+good[i][1].w); 
			}
			if(j >= good[i][0].v+good[i][2].v){  //选主件+附件2 
				dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][2].v] + 
				good[i][0].w+good[i][2].w);
			}
			if(j >= good[i][0].v+good[i][1].v+good[i][2].v){  //都选 
				dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v-good[i][2].v]
				 + good[i][0].w+good[i][1].w+good[i][2].w);
			} 
		}
	}
	printf("%d", dp[n]);
	return 0;
}