3990 - 龙哥吃汉堡.avi
时间限制 : 1 秒
内存限制 : 128 MB
龙哥一日学完高数，肚子咕咕发酵，于是来到理工北门的一家汉堡店吃汉堡。当然啦，汉堡也是不一样的，有牛肉堡，有鸡肉堡，还有鳕鱼堡、田鸡堡等等。龙哥对奇奇怪怪的东西很讨厌(田鸡堡都不吃)，所以不同的汉堡龙哥吃下后会产生不同的幸福感(比如牛肉堡的幸福感高，田鸡堡的幸福感低)，我们知道龙哥胃所能容纳的体积为V，每种汉堡都有自己的体积v和幸福感x，现在给你n种汉堡(汉堡不限量)，问你如何在保证龙哥所吃的汉堡体积总和不超过胃所容纳的体积下，产生最高的幸福感。龙哥想知道他如何吃才能保证他得到最大的幸福感呢(一本满足.jpg)
题目输入
第一行输入一个 t（0 < t < 5），表示有t组测试数据；
第二行输入2个数V, n（0 < V < 100000, 0 < n < 1000），表示龙哥胃的体积为V，汉堡种类的个数为n；
接下来n行，每行输入2个数，分别表示每种物品的幸福感和体积
题目输出
输出一个整数，表示龙哥能获得的最大的幸福感是多少
输入/输出样例
输入格式
2 10 1 10 1 10 2 5 2 20 6
输出格式
100 100
C++解答
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <queue> #include <cmath> #include <string> #include <set> #include <map> #define N 1010 using namespace std ; int dp[N], w[N], c[100010] ; int main() { int t ; scanf ("%d", &t) ; while (t--) { int V, n ; scanf ("%d%d", &V, &n) ; for (int i=0; i<n; i++) scanf ("%d%d", &w[i], &c[i]) ; for (int i=0; i<n; i++) for (int v=c[i]; v<=V; v++) dp[v] = max (dp[v], dp[v-c[i]] + w[i]) ; printf ("%d\n", dp[V]) ; } return 0 ; }