hdu 1114 Piggy-Bank(完全背包)

点击打开链接hdu1114

思路: 裸完全背包

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 510;
const int MAXN = 10010;

int sum , n;
int p[N] , w[N];
int dp[MAXN];

void solve(){
    memset(dp , INF , sizeof(dp));
    dp[0] = 0;
    for(int i = 1 ; i <= n ; i++)
        for(int j = w[i] ; j <= sum ; j++)
           dp[j] = min(dp[j] , dp[j-w[i]]+p[i]); 
    if(dp[sum] != INF)
        printf("The minimum amount of money in the piggy-bank is %d.\n" , dp[sum]);
    else
        puts("This is impossible.");
}

int main(){
    int Case , x , y;
    scanf("%d" , &Case);
    while(Case--){
         scanf("%d%d" , &x , &y); 
         sum = y-x;
         scanf("%d" , &n);
         for(int i = 1 ; i <= n ; i++)
             scanf("%d%d" , &p[i] , &w[i]);
         solve(); 
    }
    return 0;
}