hdu 1114 Piggy-Bank（完全背包）

題目鏈接：hdu1114

大意：給出存錢罐本身的重量和裝錢後的重量，以及存錢罐中錢的面值和重量，求存錢罐裝滿時，錢的總和最小是多少

思路：完全背包解題，每種錢幣都可以裝無限個，注意初始化的值

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 1005
#define INF 0xffffffff
using namespace std;
int d[10005],c[505],v[505];
int main()
{
    int T,n,V,i,j,E,F;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&E,&F);
        V = F - E;
        scanf("%d",&n);
        for(i = 0 ; i < n ; i ++)
        scanf("%d%d",&v[i],&c[i]);
        for(i = 1 ; i <= V ; i ++)
        d[i] = 5000000;//初始化為正無窮，如果求錢幣的最大值的話，就初始化為負無窮
        d[0] = 0;
        for(i = 0 ; i < n ; i ++)
         for(j = c[i] ; j <= V ; j ++)
            d[j] = min(d[j - c[i]] + v[i],d[j]);
        if(d[V] == 5000000)//沒有裝滿
         printf("This is impossible.\n");
        else
         printf("The minimum amount of money in the piggy-bank is %d.\n",d[V]);
    }
    return 0;
}