Piggy-Bank—hdu1114（完全背包）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1114

题意是有一个存钱罐，当它是空的时候重量为E，满的时候重量为F；已知存钱罐里面有 n 种钱，每种钱的价值为 P 重量为 W ；求存钱罐满的时候里面至少有多少钱；

是一个完全背包(求从n个物品中选出总重量不大于W的最大价值)问题：

二维数组：

(1 <= i <=n; 0<=j<=W)

dp[i][j] = max(  dp[i-1][ j],  dp[i][ j-w[i] ]+v[i]  )(j>=w[i]);

　　　　=dp[i-1][j];(j<w[i]);

一维数组：

（1<=i<=n; w[i]<=j<=W）

dp[j]=max( dp[j], dp[ j-w[i] ]+v[i] );

而本题求得是最小价值所以稍微改一下就可以了

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 50100
#define INF 0xfffffffint dp[N], v[N], w[N], W, n;int main()
{
    int T, E, F;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &E, &F);        W = F - E;        scanf("%d", &n);
        for(int i=; i<=n; i++)
            scanf("%d %d", &v[i], &w[i]);        for(int i=; i<=W; i++)
            dp[i]=INF;
        dp[]=;        for(int i=; i<=n; i++)
        {
            for(int j=w[i]; j<=W; j++)
            {
                dp[j]=min(dp[j], dp[j-w[i]]+v[i]);
            }
        }
        if(dp[W]==INF)
            printf("This is impossible.\n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[W]);
    }
    return ;
}