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.
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
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
#include
#include
#include
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
",ans);
}
return 0;
}
///1020 0 0 0 49 1 0 0 0 1 0
※面向對象,局部變數和成員變數
※Nginx 反向代理、負載均衡
※ASP.NET CORE小試牛刀:乾貨
TAG:達人科技 |