HLG 哈理工 1053 Warcraft III （完全背包）

dccmx likes playing Warcraft III. Now, he is teaching his girlfriend to play it. In Warcraft III, there are many kinds of units. Every unit costs some gold and lumber. Different units have different attack value.

Now question comes. Given some amount of gold and a list of types of units, how to arrange your units to maximize the attack value of your units. Assume you have infinite lumbers.

Line 1 contains an integer T: the number of test cases.

Next T blocks, each starts with two integers: G and U, represents the amount of gold and number of unit type. Next U lines, each contains two integers: the attack value of a type of unit and the cost.

For each test case, output the maximum total attack value in one line.

2

100 1

20 10

300 4

100 60

250 120

120 100

35 20

200

605

dccmx

/*=============================================================================
#
#      Author: liangshu - cbam 
#
#      QQ : 756029571 
#
#      School : 哈尔滨理工大学 
#
#      Last modified: 2015-08-29 00:24
#
#     Filename: C.cpp
#
#     Description: 
#        The people who are crazy enough to think they can change the world, are the ones who do ! 
=============================================================================*/
#
#include<stdio.h>
#include<iostream>
using namespace std;

const int INF = 100000;
int dp[INF];
struct A
{
    int val,cost;
}E[INF];
int main(){
    int T;
    cin>>T;
    while(T--){
        int G, U;scanf("%d%d",&G, &U);
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= U; i++){
            scanf("%d%d",&E[i].val, &E[i].cost);
        }
        for(int i = 1; i <= U; i++){
            for(int j = E[i].cost; j <= G; j++){
                dp[j] = max(dp[j], dp[j - E[i].cost] + E[i].val);
            }
        }
     printf("%d\n",dp[G]);
    }
    return 0;
}