HDU 1144 Piggy-Bank

题意：有这么个存钱罐，给你空的时候重量和满的时候的重量，再给你N中类型的硬币（给出N种硬币总数量和总重量，可多次使用），问你怎样恰好填满存钱罐，而让填入的硬币数量最少。

思路：完全背包，求最少填入硬币数量，要把dp数组全部填充为INF，求min，注意结果要恰好填满。

dp[j]= min(dp[j],dp[j-w[i]]+v[i])(dp[j]代表当前步，所用硬币最小数目)

/**

Sample Input

3

10 110

2

1 1

30 50

10 110

2

1 1

50 30

1 6

2

10 3

20 4 

Sample Output

The minimum amount of money in the piggy-bank is 60.

The minimum amount of money in the piggy-bank is 100.

This is impossible.

**/

#include <cstdio>

#include <cstring>

#include <utility>

#include <algorithm>

using namespace std;

int const INF = 0x3f3f3f3f;

int E,F,N;

int dp[10005];

pair<int ,int >coin[505];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        memset(dp,INF,sizeof(dp));

        scanf("%d%d%d",&E,&F,&N);

        int last = F-E;

        for(int i=0;i<N;i++){

            scanf("%d%d",&coin[i].first,&coin[i].second);

        }

        dp[0] = 0; //注意这里dp[0]要赋值为0

        for(int i=0;i<N;i++){

            for(int j=coin[i].second;j<=last;j++){

                    dp[j] = min(dp[j],dp[j-coin[i].second]+coin[i].first);

            }

        }

        if(dp[last]!=INF)

            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[last]);

        else printf("This is impossible.\n");

    }

    return 0;

}