reset password
Author Message
raylongma1018
Posts: 81
Posted 20:18 Jul 08, 2015 |

for coin change problem it doesn't state the condition we want.It could be "return most number of coins to the customers "(so we return 14 1cents) or least coins(can't apply greedy algorithm). it also doesn't tell us how many coins we have for each values(7cents, 1cents,10cents). so the solution doesn't tell us what kind of greedy algorithm apply. 

Since this problem doesn't state requirement for the coin change and also the textbook doesn't provide any similar example for coin change problem so we are not able to do this problem.

Solution for this problem is meaningless

jpatel30
Posts: 18
Posted 21:56 Jul 08, 2015 |

In this question you have been asked the qustion that you need to solve using greedy technique . 

so you need to apply the greedy algorithm .

If you do that you will be having three set of optimal solution but the most optimal will be 1*4+1*10 . So that is also not meaningless . 

Last edited by jpatel30 at 21:57 Jul 08, 2015.
raylongma1018
Posts: 81
Posted 22:01 Jul 08, 2015 |

so what does 1*4 and 10*1 tells you?

jpatel30
Posts: 18
Posted 22:04 Jul 08, 2015 |

It is clear in the question that you have coins of 1,7,10 cents

so 4 coins of 1cent and 1 coin of 10 cent 

can you please read the question properly .

Follow the knapsack 0-1 problem you will be able to understand the ans.

If you have any other doubt let me know .

Thanks 

 

raylongma1018
Posts: 81
Posted 22:13 Jul 08, 2015 |

the difference between this problem and the knap-sack 0-1 problem is that in knap-sack 0-1 problem tells you the goal you need to solve in our textbook we need to carrry most valuable items 

but in this problem it does not tell us the goal, well maybe we can say return 14 cents to the customers then, they will be many possible ways to returns coins to customers, one one is return 14 1 cents so you return 14 coins, or 2 7 cents (you return least coins) , or maybe 4 1 cents and 1 10 cents or 1 7 cents or 7 1 cents the question never set any restriction to how many coins we have that means we have unlimted amount of 1,7,10 cents. 

Since the question does not tell us what kind goal we looking for, we can assume that our goal is to find the optimal way to return most number of coins to custmoers when returning 14 cents. then answer will be 14 1 cents

jpatel30
Posts: 18
Posted 22:15 Jul 08, 2015 |

It is mention in the question that what will be the answer if we use greedy algorithm .

plakhan
Posts: 37
Posted 22:16 Jul 08, 2015 |

It states that you have to choose a greedy algorithm. Which means you should first consider the highest possibly value which is in this case 1 coin of 10 cent inorder to reach 14 cents

raylongma1018
Posts: 81
Posted 22:25 Jul 08, 2015 |

ok why we can't pick 1 cents first instead of 10 cents if we want to apply greedy algorithm?

since our goal is to return 14 cents to the custormers, and I am the merchant I want to find the optimal way to get rid of all my smallers coins first before spend the biggers coins, then i will spend all the 1 cents coins first before i spend bigger coins.

since the number of coins per each value is unlimited that means making a greedy choice in reverse way (return smaller coins frist) is workable unless there is a restriction on the number of coins for each values then we have to return bigger coins first (10 cents then 1 cents) 

raylongma1018
Posts: 81
Posted 22:30 Jul 08, 2015 |

from the textbook the greedy-algorithm chapter all the examples like knap-sack or activity -selection problems or shortest path they all have set restriction on their elements so we know what situation should or should not apply a greedy algorithm. 

the element in this question is the number of coins for each values, but the problem is this questions never tells how many coins the merchant have that means it could be unlimited, (we not talking about real world, we are talking about math), if all the coins number are unlimited then greedy choice can be work on both way

plakhan
Posts: 37
Posted 22:30 Jul 08, 2015 |

Greedy algorithms do not find any optimal way, in fact in a greedy algorithm, we make whatever choice
seems best at the moment and then solve the subproblem that remains. Greedy strategy usually
progresses in a top-down fashion, making one greedy choice after another, reducing
each given problem instance to a smaller one. I hope you undetstand the meaning of greedy choice. It means select a higher value.

raylongma1018
Posts: 81
Posted 22:35 Jul 08, 2015 |

if you claim greedy choice is always selecting a higher value then activity-selection is wrong.

if we want a higher value then we shouldn't selected "smallest" finished time instead we should select "higher" or "highest" finishing time. 

Correct me if I am wrong

raylongma1018
Posts: 81
Posted 22:50 Jul 08, 2015 |

since the finishing time is in terms of numbers in mathematical point of view

if we consider finishing time in terms of numbers then we should pick the smaller number first as our greedy choice

greedy choice could be confusing sometimes. for the coin change problem if we set the number of 1 cents to be only 2 then greedy choice won't work. that means we need to use dynamic programming

from the textbook all the examples tells us how many elements it contains. so we can know whether we need to apply greedy choice or not. if the restriction prohibits us to reach the optimal solution by making a greedy choice, then we have to find other greedy choice or dynamic programming. but none of the examples has ever talks about when the elements is unlimited. like this problem.