4

I was reading through an example question for the UNSW Computing ProgComp and found a question they claimed to be impossible to solve without going through all possible solutions.

From https://cgi.cse.unsw.edu.au/~progcomp/pop.php?loc=2014opentasks#task5 :

You have a length of timber that needs to be cut into several pieces. The points where the cuts have to be made are marked on the timber, measured from one end. The only precision cutting company available at short notice charges, for each cut, a rate in dollars equal to the length of the piece (being cut) in metres before cutting.

enter image description here

The order in which the cuts occur affects the total price. For example, a piece 10m long with cuts needed at 4m, 5m and 7m could be cut first at 5m, costing \$10, leaving two 5m sections requiring one cut each, a total of \$10 + \$5 + \$5 = $20.

However if the cuts are made at 4m, 7m and 5m the total cost is \$10 + \$6 + \$3 = $19."

...

There is no shortcut computational strategy that can generate the optimal cost in all cases, though heuristics may work sometimes. Instead you should try all possible cut sequences. Small-scale problems can be solved by a simple recursive design, but will take an inordinate amount of time for larger numbers of cuts as the number of small, repeated subproblems escalates exponentially.

Solving large problems of this kind requires a technique called dynamic programming, where the the first time each small subproblem is solved, the solution is stored in an array or hash, representing a solution cache. When the same subproblem needs to be solved again the cache is first inspected, thus avoiding possibly thousands of recalculations.

While as a programming problem it would be easy to go through all the possible solutions, I'm curious to see if there's a way to do so mathematically.

Chris Culter
  • 26,806
Teco
  • 161
  • @Arthur The dynamic programming solution would seem to take only $O(n^3)$ time. – Chris Culter May 24 '16 at 05:04
  • It reminds me of determining the most efficient way to multiply a collection of matrices (I don't know that they are that similar, but it feels like associativity may be central here too). – pjs36 May 24 '16 at 05:18

1 Answers1

1

Here is a way to "figure out" the intended dynamical programming approach from the perspective of mathematical induction. Denote the length of the pieces from left to right by $(a_1, \dots, a_n)$. We want to find the minimal charge $f(a_1, \dots, a_n)$.

Now let's try to argue using mathematical induction. The base case is when we have one number: $a_1$. Apparently, we have nothing to do in this case and the total penalty is 0. Now suppose we know how to deal with $k$ pieces for all $k < n$ and we want to know how to deal with $n$ pieces: $a_1, \dots, a_n$. The first cut might happen between $(a_1, \dots, a_i)$ and $(a_{i+1}, \dots, a_n)$ for some $i = 1, \dots, n-1$. We need to pay $a_1 + \dots + a_n$. And by the induction hypotheses, we know how to cut both $(a_1, \dots, a_i)$ and $(a_{i+1}, \dots, a_n)$ economically. Hence we get $$f(a_1, \dots, a_n) = a_1 + \dots + a_n + \min_{1\le i < n}\left\{f(a_1, \dots, a_i)+f(a_{i+1}, \dots, a_n)\right\}$$

From here, one can figure out the dynamical programming algorithm with time complexity $O(n^3)$.

Zilin J.
  • 4,270