Greedy algorithms and dynamic programming: 5. Suppose we want to cut board of lu
ID: 3560584 • Letter: G
Question
Greedy algorithms and dynamic programming:
5. Suppose we want to cut board of lumber in sawmill. The mill charges by length of
each board. For example, to cut anywhere on a 10 ft. board of lumber costs $10. The
overall cost of cutting a single board into smaller pieces depends on the order of the cuts.
As input, you are given a board of length n with k locations to cut along the board. For
example a board may looks like the following.
This represents a lumber with 29ft long and we need to cut at 4 locations. If we follow
the cutting order of 4, 14, 19, 27, the overall cost will be
29 + 25 + 15 + 10 = 79
The problem is that we wish to produce a cutting order with minimum cost.
Suppose there is a solution suggests that we always choose to cut a piece as close as
possible to the center of the initial board. Does this produce an optimal solution? Why or
why not? (Note: you can use examples to illustrate your solution)
Explanation / Answer
And my attempt at interpreting what's going on :
Greedy choice property We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.