IOS遗忘的知识
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 7626 | Accepted: 3665 |
Description
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
Input
Output
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.
完全背包。。。。。
AC代码如下:
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<climits> #define M 100005 using namespace std; int main() { int m,e,f,t; int i,j; int a[M],b[M],dp[M]; scanf("%d",&t); while(t--) { scanf("%d%d",&e,&f); f-=e; scanf("%d",&m); for(i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]); for(i=1;i<=f;i++) dp[i]=INT_MAX/2;//实验证明背包还是不要取最大了 //printf("%d\n",dp[f]); for(i=1,dp[0]=0;i<=m;i++) { for(j=b[i];j<=f;j++) if(dp[j]>dp[j-b[i]]+a[i]) dp[j]=dp[j-b[i]]+a[i]; } if(dp[f]!=INT_MAX/2) printf("The minimum amount of money in the piggy-bank is %d.\n",dp[f]); else printf("This is impossible.\n"); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。