Piggy-Bank

完全背包。。。

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

#define INF  0x3f3f3f3f

struct node
{
    int P;
    int W;

    bool operator <(const struct node &A)
    {
        return this->W < A.W;
    }
};

typedef struct node Node;

Node A[510];

int dp[10100];

int T;
int N;

int main()
{
    freopen("G:\\data.txt", "r", stdin);

    int E, F;
    cin >> T;

    while(T--)
    {
        cin >> E >> F;

        cin >> N;

        for(int i = 0; i < N; i++)
        {
            cin >> A[i].P >> A[i].W;
        }

        sort(A, A + N);

        int V = F - E;

        for(int i = 1; i <= V; i++)
        {
            dp[i] = INF;
        }

        for(int i = 0; i < N; i++)
        {
            for(int j = 1; j <= V; j++)
            {
                if(A[i].W <= j)
                {
                    dp[j] = min(dp[j], dp[j-A[i].W]+A[i].P );
                }
            }
        }
        if(dp[V] >= INF)
        {
            cout << "This is impossible." << endl;
        }else
        {
            cout << "The minimum amount of money in the piggy-bank is "<< dp[V] << "."<< endl;
        }
    }

    return 0;
}