DP(四)——簡單的完全背包2
POJ 1384 http://poj.org/problem?id=1384
題意：用豬仔錢罐存錢會有一個嚴重的問題：不能隨時知道里面到底有多少錢。
但是，我們可以通過稱量其重量，來估計一下里面的錢。
現假定錢罐里的都是硬幣，已知空罐的重量與現在的重量，同時，給定錢罐里可能會有的硬幣的面額與重量。
問錢罐中至少有多少錢。
思路：從錢罐重量差可知硬幣的總重量。每種硬幣的數量不確定，
估計時可當作有可能有無限個，由此可得完全背包模型。求的是能否組合成該重量，
組合以后的最小價值。
Sample Input
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
View Code
#include"iostream"
using namespace std;
#define INF 0xFFFFFF
#define size 11111
int f[size];
int main()
{
int i, j, t, E, F, w, n, we, va, v;
cin>>t;
while(t--)
{
cin>>E>>F;
w = F-E;
for(i=1; i<=w; i++) f[i] = INF;
f[0] = 0;
cin>>n;
for(i=0; i<n; i++)
{
cin>>va>>we;
for(v=we; v<=w; v++)
f[v] = min(f[v], f[v-we]+va);
}
if(f[w]<INF) cout<<"The minimum amount of money in the piggy-bank is "<<f[w]<<"."<<endl; //f[w]<INF表明可以恰好裝滿，即有解
else cout<<"This is impossible."<<endl;
}
}
posted on 2011-11-16 10:43 More study needed. 閱讀(203) 評論(0) 收藏 舉報
浙公網安備 33010602011771號