You have supplies of boards that are one foot, ﬁve 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 greedy algorithm of taking boards of the longest length at each stage (so long as the total length of the boards selected does not exceed 15 feet) does not give the fewest number of boards possible.

Question

Quizplus · Accepted Answer

The Answer is The greedy algorithm ﬁrst chooses a 12-foot-long board, and then three one-foot-long boards. This requires four boards. But only three boards are needed: each ﬁve feet long.

You Have Supplies of Boards That Are One Foot, ﬁVe