Greedy Algorithm Confusing Question

Question

US portal Denominations are 1,10,21,34,70 , 100 and 350 .

A) Make 140 Cents .

Verify whether Greedy choice fails or not

B) Make 182 Cents.

Verify whether greedy choice fails or not.

 

1)Greedy fails in A

2) Greedy fails in B

3)Greedy does not fails in A

4)Greedy does not fails in B

Comments

i guess Greedy fails for first one.

---

please solve what coins and how coins you will select solve completely ???

---

see for first one-we have to make 140 cents.
being greedy,we will choose the largest amount less than 140,which is 100.
left amount is 40.
so being greegy,we will choose largest coin < 40 which is 34.
left amount is 6.now only denomination of 1 only is capabale of making 6 cent by adding 6 coins of denomination 1.
so,total number of coins used are 8
but ,if we dun use greedy approach then we can make 140 cents by jut 5 coins ( 100 + 10+10+10+10) or even by just 2 coins (40 + 40)
hence,greedy fails here.
for  second ,we have to make 182 cents.
being greedy ,we will choose 100 as it is the largest coin < 182
amount left is 82
now,we will choose 70.
amount left is 12.
now,we will choose coin 10 .
amount left is 2.
now we will take 2 coins of denomination 1.
hence,total coins are (100+70+10+1+1) =5
.

and hence GReedy is beneficial in only second case

Answer 1

Case A)

Greedy --  100+34+1+1+1+1+1+1 = 8 coins

Dynamic -- 70+70= 2 coins

Case B)

Greedy -- 100+70+10+1+1 = 5 coins

Dynamic -- 70+70+21+21 = 4 coins

 

So Greedy algo. Fails in both the cases

Answer 2

see for first one-we have to make 140 cents.
being greedy,we will choose the largest amount less than 140,which is 100.
left amount is 40.
so being greegy,we will choose largest coin < 40 which is 34.
left amount is 6.now only denomination of 1 only is capabale of making 6 cent by adding 6 coins of denomination 1.
so,total number of coins used are 8
but ,if we dun use greedy approach then we can make 140 cents by jut 5 coins ( 100 + 10+10+10+10) or even by just 2 coins (40 + 40)
hence,greedy fails here.
for  second ,we have to make 182 cents.
being greedy ,we will choose 100 as it is the largest coin < 182
amount left is 82
now,we will choose 70.
amount left is 12.
now,we will choose coin 10 .
amount left is 2.
now we will take 2 coins of denomination 1.
hence,total coins are (100+70+10+1+1) =5
.

and hence GReedy is beneficial in only second case and hence option A is correct.

Answer 3

Greedy Fails in Both the cases