HDOJ-1114 Piggy-Bank

전체 가방 문제

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

using namespace std;

#define INF 1e9
int c[505], v[505], dp[10005];

int main()
{
    //freopen("in.txt", "r", stdin);
    int t;

    cin >> t;
    while(t--)
    {
        int E, F, n, m;
        cin >> E >> F >> n;
        for(int i = 0; i < n; i++)
            cin >> c[i] >> v[i];
        m = F - E;
        for(int i = 1; i <= m; i++)
          dp[i] =INF;
        dp[0] = 0;

        for(int i = 0; i < n; i++)
            for(int j = v[i]; j <= m; j++)
            dp[j] = min(dp[j], dp[j-v[i]] + c[i]);
        if(dp[m] == INF)
            cout << "This is impossible." << endl;
        else
            cout << "The minimum amount of money in the piggy-bank is " << dp[m] << "." << endl;

    }
    return 0;
}