学步园

http://poj.org/problem?id=1384

恰好装满的最小价值～

#include <stdio.h>
#include <string.h>
const int INF = 1000000000;
int  f[10010];
int main()
{
    int E, F, W, T, n, p, w,i , j;
    scanf("%d\n",&T);
    while(T--)
    {
        scanf("%d%d",&E,&F); W = F - E;
        scanf("%d",&n);
        for(i=1; i<=W; i++) f[i] = INF;
        f[0] = 0;
        for(i=0; i<n; i++)
        {
            scanf("%d%d",&p, &w);
            for(j=w; j<=W; j++)
            if(f[j]>f[j-w]+p)
                f[j] = f[j-w]+p;
        }
        if(f[W]!=INF)
        printf("The minimum amount of money in the piggy-bank is %d.\n",f[W]);
        else
            printf("This is impossible.\n");
    }
    return 0;
}