spoj 39

DP  完全背包问题 的   d[i] = min(d[i], d[i-w]+p)   d[i]表示当总重量为i时可装的最小价值

#include <cstdio>

#include <cstring>

#include <algorithm>

#define INF 100000000

using namespace std;

int d[10010];

int main()

{

    int t,n,m,wei;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m), wei = m-n;

        for(int i = 0; i <= wei; i++) d[i] = INF;

        d[0] = 0;

        scanf("%d",&m);

        for(int q = 0; q < m; q++)

        {

            int W,P;

            scanf("%d%d",&P,&W);

            for(int j = W; j <= wei; j++)

                d[j] = min(d[j], d[j-W]+P);

        }

        if(d[wei] != INF)

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

        else

            puts("This is impossible.");

    }

}