[POJ] 1384 Piggy-Bank.cpp

#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 999999999
int dp[10005];
int main()
{
    int T, E, F;
    int N, P[501], W[501];
    scanf("%d", &T);
    while (T--) {
        // Input
        scanf("%d %d %d", &E, &F, &N);
        for (int i = 0; i < N; ++i)
            scanf("%d %d", &P[i], &W[i]);

        // Initial
        F = F-E;
        fill (dp, dp+10005, INF);
        dp[0] = 0;

        // Minimum Knapsack
        for (int i = 0; i < N; ++i)
            for (int j = 0; j+W[i] <= F; ++j)
                dp[j+W[i]] = min(dp[j+W[i]], dp[j] + P[i]);

        // Output
        if (dp[F] == INF) puts("This is impossible.");
        else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[F]);
    }
}