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
Daily Recommendation