Optimally cutting a stick at specified locations
This is actually a problem from the UVa Online Judge. http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944
In this problem L < 1000 and n < 50.
As I mentioned in the comments, if you notice then for each cut, the possible lengths of stick at which the cut can be made = n.
The total possible remaining lengths
shall be finite and for each remaining length the number of sets of cuts remaining
shall also be finite. So you can build a DP on the remaining lengths.
Starting from the smallest, for each 'remaining length', you can calculate the minimum cost of cutting it down further.
Something like:
DP[k][SetOfCutsRemaining] = k + Min( DP[m1][SetOfCutsRemaining till c1]
+ DP[k-m1][SetOfCutsremaining from c1],
DP[m2][SetOfCutsRemaining till c2]
+ DP[k-m2][SetOfCutsremaining from c2],... )
where mi are the lengths remaining if we make a cut at ci
You will then need to do this till DP[L][InitialSetOfCuts]
.
In the example problem, L = 10, ci = 2, 4, 7
The remaining lengths and their corresponding cuts remaining are as follows. Note that the number of combinations shall be C(n+2,2) = (n+2)(n+1)/2 = 10 in this case
2 {} (2 times, 0-2 and 2-4)
3 {} (2 times, 4-7 and 7-10)
4 {c1}
5 {c2}
6 {c3}
7 {c1, c2}
8 {c2, c3}
10 {c1, c2, c3}
DP[2][{}] = 0 (No cut remaining)
DP[3][{}] = 0 (No cut remaining)
DP[4][{c1}] = 4 (1 cut remaining)
DP[5][{c2}] = 5 (1 cut remaining)
DP[6][{c3}] = 6 (1 cut remaining)
DP[7][{c1,c2}] = 7 + Min( DP[2]{} + DP[5][{c2}], DP[3]{} + DP[4][{c1}] )
= 7 + Min( 5, 4 ) = 11.
DP[8][{c2,c3}] = 8 + Min( DP[2]{} + DP[6][{c3}], DP[3]{} + DP[5][{c2}] )
= 8 + Min( 6, 5 ) = 13.
DP[10][{c1,c2,c3}] = 10 + Min( DP[2]{} + DP[8][{c2,c3}], DP[4]{c1} + DP[6][{c3},
DP[7][{c1,c2}] + DP[3]{} )
= 10 + Min( 13, 10, 11 ) = 20.
First, assuming we have an ascending-order array of cutting position, so in OP example, it will be {2,4,7}
At first, we have the stick with length from 0 to n, so we call function
int cal(int start, int end , int [] cuts)
with start = 0 and end = n.
For every cutting point which is greater than start and less than end, we have the formula
int result = 1000000;
for(int i = 0; i < cuts.length; i++){
if(cuts[i]> start && cuts[i]<end){
int val = (end - start) + cal(start, cuts[i], cuts) + cal(cuts[i],end , cuts);
result = min(val, result);
}
}
and the DP table can be simply
dp[start][end]
So, the whole solution will be:
int cal(int start, int end, int[]cuts){
if(dp[start][end]!= -1){//Some initializations need to be done
return dp[start][end];
}
int result = 1000000;
for(int i = 0; i < cuts.length; i++){
if(cuts[i]> start && cuts[i]<end){
int val = (end - start + 1) + cal(start, cuts[i], cuts) + cal(cuts[i],end , cuts);
result = min(val, result);
}
}
return dp[start][end] = result;
}
To further enhance the space using, we can refer each cut position as its index in the array cuts
.
Added start and end point to the cut arrays, we have following arrays
{0,2,4,7,10}
By referring to start position as index 0, end as index 4, we can decrease the space of array dp from dp[10][10] to dp[5][5]
One more DP solution:
Let's COST(a,b) is the best cost of cutting the segment between a-th and b-th cut point. It is clear that COST(a,a) and COST(a,a+1) is zero. We can compute the best value of COST(a,b) as minimum of cuts through all the middle points a+1...b-1 plus own segment length. So we can fill triangle table diagonal by diagonal and find final result as COST(start,end) with O(N^3) time complexity and O(N^2) space
Delphi code (outputs Cost 20 Sequence 4 2 7
)
var
Cuts: TArray<Integer>;
Cost: array of array of Integer;
CutSequence: array of array of String;
N, row, col, leftpos, rightpos, cutpos, Sum: Integer;
begin
Cuts := TArray<Integer>.Create(0, 2, 4, 7, 10); // start, cuts, end points
N := Length(Cuts);
SetLength(Cost, N, N); //zero-initialized 2D array
SetLength(CutSequence, N, N); //zero-initialized 2D array
for rightpos := 2 to N - 1 do
for leftpos := rightpos - 2 downto 0 do begin //walk along the diagonals
//using previously computed results
//find the best (mincost) cut
Cost[leftpos, rightpos] := MaxInt; //big value
for cutpos := leftpos + 1 to rightpos - 1 do begin
Sum := Cost[leftpos, cutpos] + Cost[cutpos, rightpos];
if Sum < Cost[leftpos, rightpos] then begin
Cost[leftpos, rightpos] := Sum;
//write down best sequence
CutSequence[leftpos, rightpos] := Format('%d %s %s', [Cuts[CutPos],
CutSequence[leftpos, cutpos], CutSequence[cutpos, rightpos]]);
end;
end;
//add own length
Cost[leftpos, rightpos] :=
Cost[leftpos, rightpos] + Cuts[rightpos] - Cuts[leftpos];
end;
//show the best result
Caption := Format('Cost %d Sequence %s',[Cost[0, N-1], CutSequence[0, N-1]]);