爱华网Piggy-Bank
TimeLimit: 2000/1000 MS(Java/Others)MemoryLimit: 65536/32768 K (Java/Others)Total Submission(s):7675AcceptedSubmission(s): 3837
Problem DescriptionBefore ACM can do anything, a budget must be prepared and thenecessary financial support obtained. The main income for thisaction comes from Irreversibly Bound Money (IBM). The idea behindis simple. Whenever some ACM member has any small money, he takesall the coins and throws them into a piggy-bank. You know that thisprocess is irreversible, the coins cannot be removed withoutbreaking the pig. After a sufficiently long time, there should beenough cash in the piggy-bank to pay everything that needs to bepaid.
But there is a big problem with piggy-banks. It is not possible todetermine how much money is inside. So we might break the pig intopieces only to find out that there is not enough money. Clearly, wewant to avoid this unpleasant situation. The only possibility is toweigh the piggy-bank and try to guess how many coins are inside.Assume that we are able to determine the weight of the pig exactlyand that we know the weights of all coins of a given currency. Thenthere is some minimum amount of money in the piggy-bank that we canguarantee. Your task is to find out this worst case and determinethe minimum amount of cash inside the piggy-bank. We need yourhelp. No more prematurely brokenpigs!
InputThe input consists of T test cases. The number of them (T) is givenon the first line of the input file. Each test case begins with aline containing two integers E and F. They indicate the weight ofan empty pig and of the pig filled with coins. Both weights aregiven in grams. No pig will weigh more than 10 kg, that means 1<= E <= F <= 10000. Onthe second line of each test case, there is an integer number N (1<= N <= 500) that gives the number ofvarious coins used in the given currency. Following this areexactly N lines, each specifying one coin type. These lines containtwo integers each, Pand W (1 <= P <=50000, 1 <= W <=10000). P is thevalue of the coin in monetary units, W is it's weight ingrams.
OutputPrint exactly one line of output for each test case. The line mustcontain the sentence "The minimum amount of money in the piggy-bankis X." where X is the minimum amount of money that can be achievedusing coins with the given total weight. If the weight cannot bereached exactly, print a line "This isimpossible.".
Sample Input3 10110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4
Sample OutputTheminimum amount of money in the piggy-bank is 60. The minimum amountof money in the piggy-bank is 100. This is impossible.
SourceCentral Europe 1999
RecommendEddy
解决代码：#include<iostream>using namespace std;
int main(){ int t; cin>>t; while(t--) { int e,f,n,p[50001],w[10001],temp[10001]; cin>>e>>f; cin>>n; for(int i=1;i<=n;++i) { cin>>p[i]>>w[i]; } for(int i=1;i<=f-e;++i) { temp[i]=INT_MAX; } temp[0]=0; for(int i=1;i<=n;++i) { for(intj=w[i];j<=f-e;++j) { if(temp[j-w[i]]!=INT_MAX) { if(temp[j-w[i]]+p[i]<temp[j]) temp[j]=temp[j-w[i]]+p[i]; } } } if(temp[f-e]<INT_MAX) cout<<"The minimum amount of money inthe piggy-bank is"<<temp[f-e]<<"."<<endl; else cout<<"This isimpossible."<<endl; } return 0;}
分析：
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。
状态转移方程为：v[i][j]=min{v[i-1][j],v[i][j-w[i]]+p[i]}。
最后，如果动规数组最后一格数据不等于初始值，即为答案。
