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.
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.
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.