one , Change problem
Examples 1：
have 1 element ,5 element ,10 element ,20 element ,100 element ,200 There are an infinite number of yuan notes . Now pay with these banknotes X element , How many banknotes do you need at least .
X = 628
Best payment method ：
3 Zhang 200 Block ,1 Zhang 20 Block ,1 Zhang 5 Block ,3 Zhang 1 Block
Common demand 3+1+1+3 = 8 Zhang
Intuition tells us : Use banknotes with larger denominations as much as possible !
Greedy : Follow a certain law , Algorithm design method of greedy selection of current optimal strategy .
analysis ： Denomination is 1 element ,5 element ,10 element ,20 element ,100 element ,200 element , Any denomination is a multiple of a denomination smaller than itself .
So when you use a larger bill , If it is replaced with notes of smaller denomination , More bills of other denominations must be needed !
code implementation ：
#include
#include
using namespace std;
int main(){
const int RMB[]= {200,100,20,10,5,1};
const int NUM = 6;//6 Species face value
int X = 628;
int count = 0;
for(int i= 0;i< NUM;i++){
int use = X / RMB[i]; Denomination required RMB[i] of use Zhang
count + = use;
X = X -RMB[i] * use;
printf(" Denomination required %d of %d Zhang ",RMB[i],use);
printf(" Remaining amount to be paid %d.\n",X);
}
printf(" Total required %d Zhang \n",count);
return 0;
}
Why? It must be right ?
Denomination is 1 element ,5 element ,10 element ,20 element ,100 element ,200 element , Any denomination is a multiple of a denomination smaller than itself .
So when you use a larger bill , If smaller denomination notes are used for replacement , More bills of other denominations must be needed .
for example ：
5=1+1+1+1+1
10=5+5
20=10+10
100=20+20+20+20+20
200=100+100
so ： The current optimal solution is the global optimal solution , Greedy establishment .
Examples 2：
have 1 element ,5 element ,6 Yuan note , Now pay with these bills K element , How many notes at least ?
After our analysis , This situation is not suitable for greedy algorithm , Because the greedy strategy we provided above is not the optimal solution . such as , To pay 10 Yuan words , According to the above algorithm , At least 1 Zhang 6 Meta ,4 Zhang 1 Meta , In fact, the best should be 2 Zhang 5 Meta .
Examples 3： hypothesis 1 element ,2 element ,5 element ,10 element ,20 element ,50 element ,100 The notes of yuan are a,b,c,d,e,f,g Zhang . Now we have to pay with this money m element , At least how many notes should I use ? If you can pay, output the minimum number of sheets paid , If you can't pay , output -1.
#include
#include
using namespace std;
const int N=7;
int Count[N]={3,0,2,1,0,3,5}; // Quantity of each denomination
int Value[N]={1,2,5,10,20,50,100}; // face value
int solve(int money)
{
int num=0;
for(int i=N-1;i>=0;i--)
{
int c=min(money/Value[i],Count[i]);
money=money-c*Value[i];
num+=c;
}
if(money>0) num=-1;
return num;
}
int main()
{
int money;
cin>>money;
int res=solve(money);
if(res!=-1) cout<
else cout<
}
Think about it , If the number of notes with different denominations is limited , Can we use greedy algorithm directly .
Return to directory ： algorithm
Last ： Basic concepts
Post Views:
278
Technology