758 views
2 votes
2 votes
Assume coins with denominator 20,15,5 and 1 are available ,we are required to make a sum of 33,using minimum number of coins.Difference between answer using greedy technique and correct answer will be ____________

2 Answers

1 votes
1 votes

using greedy:

20+5+5+1+1+1

total no of coins =6

dynamically:

15+15+1+1+1

total no of coins =5

difference = 6-5 =1

edited by
0 votes
0 votes
Given the coins with denominations 20,15,5 and 1 we have to generate a sumof 33 with the help of minimum number of coins.

Approach 1: Greedy Approach

In order to minimize the number of coins we have to choose the coins with the maximum denomination(more the denomination of the coin less is the number of the coins required). So the required value is 33. Coin with maximum denomination 20 is chosen as 20<33 we can use it so current value left=13 no. of coins=1. We can't use the coin with denomination 15 as current value is less than it. So the next highest denomination is  5 . We use 2 coins of denomination 5. total no of coins currently=3. value left=3. Next we use 3 coins of denomination 1 . total coins =3+3 =6.

By following greedy approach we get 6 coins.

Approach 2:Dynamic Programming

Dynamic programming uses the bottom up approach . We will check by which way we are getting the minimum number of coins starting with coins of :

Denomination  1: No. of coins=33

Denomination 1,5 : No. of coins=6+3=9

Denomination 1,5,15:No of Coins=2+3=5

Denomination 1,5,15,20: No. of Coins=1+2+3=6 but as the no. of coins we got in the previous steps are less we go with them.

So by following dynamic programming we get no of coins=5.

The difference is :6-5=1.

Related questions

4 votes
4 votes
3 answers
1
Lakshman Bhaiya asked Nov 10, 2018
12,299 views
If job $J=(J_{1},J_{2},J_{3},J_{4})$ are given their processing time $T_{i}=(1,1,2,3)$ and deadline are $D_{i}=(3,4,2,3)$ maximum how many job can be done$?$$A)1$ ...
0 votes
0 votes
1 answer
3
Na462 asked Apr 30, 2018
4,369 views
Consider the following message:The number of bits required for huffman encoding of the above message are __________?My Strategy:- But the answer given is 52bits i used st...
1 votes
1 votes
1 answer
4
Tuhin Dutta asked Dec 13, 2017
6,300 views
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.Is the above statement correct?