hdu 1114Piggy-Bank(完全背包)

题意：给出存钱罐空和满的时候的重量，然后给出n种钱币，计算存钱罐满的时候存钱罐内最少有多少枚钱币

分析：完全背包问题，恰好装满，只要把dp[0]设为0，其他的设为INF（表示一个不可能达到的数，注意取得数不要再+-中超过精度)

这样就能保证值不为INF的都能找到一条从0到i的路径

#include<iostream>
using namespace std;
const int INF=0xFFFFFFF;
int dp[100010];

int main(){
    int E,F,v;
    int T;
    int n;
    int p,w;
    cin>>T;
    while(T--){
        cin>>E>>F;
        v=F-E;
        cin>>n;
        dp[0]=0;
        for(int i=1;i<=v;i++)
            dp[i]=INF;
        for(int i=0;i<n;i++){
            cin>>p>>w;
            for(int j=w;j<=v;j++)
                dp[j]=min(dp[j],dp[j-w]+p);
        }
        if(dp[v]!=INF)
            cout<<"The minimum amount of money in the piggy-bank is "<<dp[v]<<".
";
        else
            cout<<"This is impossible.
";
    }
    return 0;
}