首页 > 代码库 > HDU 5527---Too Rich(贪心+搜索)
HDU 5527---Too Rich(贪心+搜索)
题目链接
Problem Description
You are a rich person, and you think your wallet is too heavy and full now. So you want to give me some money by buying a lovely pusheen sticker which costs pdollars from me. To make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.
For example, if p=17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.
For example, if p=17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.
Input
The first line contains an integer T indicating the total number of test cases. Each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number ci means how many coins/banknotes in denominations of i dollars in your wallet.
1≤T≤20000
0≤p≤109
0≤ci≤100000
1≤T≤20000
0≤p≤109
0≤ci≤100000
Output
For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. If you cannot pay for exactly p dollars, please simply output ‘-1‘.
Sample Input
3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0
Sample Output
9
-1
36
题意:给了 p 表示要付的钱数,一个数列v[10],分别表示 1 ,5,10,20,50,100,200,500,1000,2000 元的钱币数量,求用尽量多的钱币刚好付清 p 元,输出钱币数。
思路:贪心,尽量用面值小的钱币去筹,但是很可能面值小的钱币不够,所以从大面值开始考虑。初始化一个前缀和sum[12],sum[i]表示v[1]~v[i]面值的钱币和,tmp=rest-sum[i-1],表示当前面值的钱币应该付多少,cn=tmp/v[i] ,即表示当前面值的钱币应该拿出多少张,如果tmp%v[i]!=0 ,那么cn++,因为小于v[i]的钱币无法筹出足够的钱;另外要对于P=50 钱币为 20,20,20,50 时,按照贪心策略3张20为60,所以不会取50,但是用3张20 无法筹出50元,所以必须每张面值的钱币应该多考虑一张,比如对于这样的数据:
p=1020 0 0 0 49 1 0 0 0 1 0;
代码如下:
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;int v[12]={0,1,5,10,20,50,100,200,500,1000,2000};int c[12],sum[12];int p,ans;void dfs(int i,int rest,int count){ if(rest<0) return ; if(i==0) { if(rest==0) ans=max(ans,count); return ; } int tmp=max(0,rest-sum[i-1]); int cn=tmp/v[i]+(tmp%v[i]!=0); if(cn<=c[i]) dfs(i-1,rest-cn*v[i],count+cn); cn++; if(cn<=c[i]) dfs(i-1,rest-cn*v[i],count+cn);}int main(){ ///cout << "Hello world!" << endl; int T; cin>>T; while(T--) { scanf("%d",&p); for(int i=1;i<=10;i++) scanf("%d",&c[i]); sum[0]=0; for(int i=1;i<=10;i++) sum[i]=sum[i-1]+v[i]*c[i]; ans=-1; dfs(10,p,0); printf("%d\n",ans); } return 0;}///1020 0 0 0 49 1 0 0 0 1 0
HDU 5527---Too Rich(贪心+搜索)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。