P240 Piggy-Bank

完全背包问题，从前往后扫。注意和01背包的区别。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXF = 10001;
const int MAXN = 501;
const int INF = INT_MAX / 10;

int value[MAXN];
int weight[MAXN];
int dp[MAXF];

int main(){
    int t;
    cin >> t; 
    while(t--){
        int e, f, n;
        scanf("%d %d", &e, &f);
        int total = f - e;
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            cin >> value[i] >> weight[i];
        }
        for(int i = 0; i <= total; i++){
            dp[i] = INF;
        }
        dp[0] = 0;
        for(int i = 0; i < n; i++){
            for(int j = weight[i]; j <= total; j++){
                dp[j] = min(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        if(dp[total] == INF) {
            printf("This is impossible.\n");
        }else{
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[total] );
        }

    }
    return 0;
}