Rod Cutting Option

Question

You are given a wooden stick of length X with the m mark on it in arbitrary places (solid), and the marking tells where the cuts should be made. For grinding sticks of length L into two parts, the carpenter charges L dollars (it does not matter whether the two parts are of the same length or not, i.e. the cost of grinding does not depend on the place of grinding). Create a dynamic programming algorithm that calculates the minimum total cost.

Failed to find out the repetition. This was requested in a recent programming interview.

Answer 1

With labels m you have m + 2 interesting points, 0 = left endpoint, marks 1, ..., m, right endpoint = (m + 1).
Store the distance from point 0 to point i in the array to calculate costs.
Edit: (Doh, provided an unnecessary loop for free, noticing after seeing what kind of answer again)
For each 0 <= l < r <= m+1 let cost[l][r] be the lowest cost to completely grind a piece between points l and r. The solution is cost[0][m+1] .

 // Setup int pos[m+2]; pos[0] = 0; pos[m+1] = X; for(i = 1; i <= m; ++i){ pos[i] = position of i-th mark; } int cost[m+2][m+2] = {0}; for(l = 0; l < m; ++l){ // for pieces with only one mark, there no choice, cost is length cost[l][l+2] = pos[l+2]-pos[l]; } // Now the dp for(d = 3; d <= m+1; ++d){ // for increasing numbers of marks between left and right for(l = 0; l <= m+1-d; ++l){ // for all pieces needing d-1 cuts // what would it cost if we first chop at the left most mark? best_found = cost[l+1][l+d]; for(i = l+2; i < l+d; ++i){ // for all choices of first cut, ssee if it cheaper if (cost[l][i] + cost[i][l+d] < best_found){ best_found = cost[l][i] + cost[i][l+d]; } } // add cost of first chop cost[l][i][l+d] = (pos[l+d] - pos[l]) + best_found; } } return cost[0][m+1]; 

Difficulty: if you naively check all possible chopping methods, m will do it! the way. Very bad. Taking into account that after any cut it doesn’t matter if you first chop off the left part, then the right one or alternately chopping the two parts, the complexity (for m> = 2) comes down to 2*3^(m-2) . Still very bad.
For our dp:

• the innermost cycle, cycle i; d-1 (l <l + d)
• cycle along l: m + 2-d (0 <= l + m + 1-d), makes (m + 2-d) * (d-1)
• the extreme loop, 3 <= d <= m + 1, is approximately m ^ 3/6 steps.

Well, O (m ^ 3) not everyone dreams, but this is the best I could come up with quickly (after some inspiration from Per post I noticed that inefficiency used to be).

Answer 2

Calculate for each pair (marking | endpoint) the cheapest way to cut off this segment of the bar. For each segment, minimize the selection of the first cuts in that segment.

Answer 3

I assume that you want the carpenter to cut once, and then continue to chop until the sticks are cut and you ask for order to make cuts?

in this case, one way to do this is to do a recursive depth search in the tree of possible combinations, where you calculate the cost as you receive, write down the first sequence and its cost and from this point forward, avoid descending into trees where the cost is higher, and always write down any cheaper sequences you find.