首页 > > 程序设计 > C/C++ >

HDU 5527---Too Rich（贪心+搜索）

2018-06-17 22:12:13来源：未知阅读 ()

题目链接

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

Input

The first line contains an integer

Output

For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly

Sample Input

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

-1

题意：给了 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