首页 > 其他 > 详细

hdu2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活 (这个只是题目名字) (多重背包)

时间:2014-05-04 00:32:56      阅读:538      评论:0      收藏:0      [点我收藏+]

本文出自:http://blog.csdn.net/svitter


原题:http://acm.hdu.edu.cn/showproblem.php?pid=2191

题意:多重背包问题。转换成为01背包解。多重背包转化为01背包的关键在于把件数从整体中孤立出来作为一个新的个体,也就是说不管分类,有多少件就有多少种。

AC代码:

//============================================================================
// Name        : 动态规划.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;
#define max(a,b) a > b ? a : b

struct Rice{
	int pr;
	int val;
};

int f[110];
Rice r[4000];

void ace(){
	//work point
	int t, i , j ,k;

	//num
	int n, m;
	int p, h, c;
	int num;//转换为01背包后的数量

	scanf("%d", &t);
	while(t--){
		memset(f, 0, sizeof(f));
		scanf("%d%d", &n, &m);

        num = 0;
		for(i = 0; i < m; i++){
			scanf("%d%d%d", &p, &h, &c);
			for(j = num; j < num + c; j++){
				r[j].pr = p;
				r[j].val = h;
			}
			num = j;
		}

		//背包最小额
		for(i = 0; i < num; i++){
			for(j = n; j >= r[i].pr; j--){
				f[j] =  max(f[j], f[j - r[i].pr] + r[i].val);
			}
		}

		printf("%d\n", f[n]);
	}
}

int main() {
	ace();
	return 0;
}


hdu2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活 (这个只是题目名字) (多重背包),布布扣,bubuko.com

hdu2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活 (这个只是题目名字) (多重背包)

原文:http://blog.csdn.net/svitter/article/details/24904105

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!