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

本文主要是介绍hdu2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活 （这个只是题目名字） （多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文出自：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 : bstruct Rice{int pr;int val;
};int f[110];
Rice r[4000];void ace(){//work pointint t, i , j ,k;//numint 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汶川大地震遇难同胞——珍惜现在，感恩生活 （这个只是题目名字） （多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---