poj 1384 Piggy-Bank （完全背包）

题目链接：。。。。。。。。。

题目大意：给出n种面值的硬币，每种面值的硬币有一定的重量， 给出存钱罐的净重和存钱罐装满的重量， 要求求出存钱罐里最少有多少钱

完全背包求解

code：

#include <stdio.h>#include <string.h>int main(){    int i = 0, j = 0, t = 0, e = 0,  f = 0, n = 0, p[502], w[502], dp[10002];    scanf("%d",&t);    while(t--)    {        scanf("%d %d %d", &e, &f, &n);        f -= e;        memset(dp, -1, sizeof(dp));        for(i = 0; i<n; i++)            scanf("%d %d",&p[i], &w[i]);        dp[0] = 0;        for(i = 0; i<n; i++)        {            for(j = w[i]; j<=f; j++)//重量            {                if(dp[j-w[i]] != -1 && dp[j] == -1)                    dp[j] = dp[j-w[i]]+p[i];                else if(dp[j-w[i]] != -1 && dp[j] != -1)                    dp[j] = dp[j]> dp[j-w[i]]+p[i]? dp[j-w[i]]+p[i]:dp[j];            }        }        if(dp[f] == -1)            printf("This is impossible.\n");        else            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[f]);    }    return 0;}