Piggy-Bank（HDU 1114）(完全背包)

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1114

題意：我們知道存錢罐存放的coins的重量為C，有N種coin，每種coin有兩種屬性：p（價值），w（重量），該重量下讓我們求最少的coins的價值。

題解：

我們用dp[ i ]來表示重量為i的時候最少的金币價值。

我們對dp進行初始化，因為price的範圍在[1,5e4]，然後dp是price疊加的是以保險起見還是用INF進行初始化。再者的話，對dp進行初始化的時候應該是按照重量的範圍，而不是金币的種類數。（卡了三天就卡在了這兩點QAQ，這個事情還告訴我，當局者迷，旁觀者清QAQ，這句話當真沒錯，我幹嘛不重新敲一遍，一直看看看，還看不出來什麼QAQ）

然後的話就是很正常的完全背包了，取最小值即可。

代碼：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <list>
#include <map>
#define P(x) x>0?x:0
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef vector<int>:: iterator VITer;
const int maxc=1e4+5;
const int maxN=505;

int dp[maxc];//maxc重的貨币的最小價值
int N,E,F,C;
struct node
{
    int p,w;
    node(int a=0,int b=0):p(a),w(b){}
    friend bool operator < (node n1,node n2)
    {
        return n1.w>n2.w;
    }
}coin[maxN];
void init()
{
    for(int i=0;i<maxc;i++)
    {
        dp[i]=INF;//price的範圍在[1,5e4],更何況dp是price疊加的是以保險起見還是用INF
    }
    dp[0]=0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&E,&F);
        C=F-E;//貨币的重量，有可能為0
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
        {
            scanf("%d%d",&coin[i].p,&coin[i].w);//有N種貨币
        }
        for(int i=1;i<=N;i++)//N種貨币
        {
            for(int j=coin[i].w;j<=C;j++)//重量一定
            {
                dp[j]=min(dp[j],dp[j-coin[i].w]+coin[i].p);
            }
        }
        if(dp[C]==INF)
            printf("This is impossible.\n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[C]);
    }
    return 0;
}