1. You have supplies of boards that are one foot, five feet, seven feet, and twe
ID: 2900733 • Letter: 1
Question
1. You have supplies of boards that are one foot, five feet, seven feet, and twelve feet long. You need to lay pieces end-to-end to make a molding 15 feet long and wish to do this using the fewest number of pieces possible. Explain why the gree
2. Prove or disprove that the greedy algorithm for making change always uses the fewest coins possible when the denominations available are pennies ( 1 -cent coins), nickels ( 5 -cent coins), and quarters ( 25 -cent coins).
3. Prove or disprove that the greedy algorithm for making change always uses the fewest coins possible when the denominations available are 1 -cent coins, 8 -cent coins, and 20 -cent coins.
I need personal answer and explanation NOT standarized answer. Thanks !
Explanation / Answer
1. If we use greedy algorithm, it will select 1 12foot board and 3 1foot boards=> 4 boards. But the optimal selection is 2 7foot boards and 1 1foot board => 3 boards. Greedy doesnt work here.
2. Here the greedy algorithm works because:
a) instead of using 5 pennies we can use 1 nickel.
b) instead of using 5 nickels we can use 1 quarter.
thus we can always minimize the total number of coins.
3. for 24 cents, the greedy algorithm chooses 1 20cent coin and 4 1cent coins => 5 coins. where as the best solution is 3 8cent coints. Hence greedy strategy wont work here. Greedy doesnt work here.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.