I am trying to figure out how to get the optimal path for a problem that can be solved with Dynamic Programming. I am interested in the case where we try to optimize for space.
To better explain my question let us consider the knapsack problem.
Let there be 3 items as follows:
I1 I2 I3
---------------------------
Val 5 4 3
Weight 4 5 2
Here the optimal path is the items that should be picked for the optimal solution.
The recurrence relations are as follows:
Let n be the nth item
let c be the remaining capacity in the knapsack
f(n, c) = 0 // if n=0
f(n, c) = f(n-1, c) // if weight[n] > c
f(n, c) = max(f(n-1, c), value[n] + f(n-1, c-weight[n])) // if weight[n] <= c
I have written a DP solution based on this recurrence relation (in java) without doing any space optimization as follows:
public static void main(String[] args) {
int[] value = {5, 4, 3};
int[] weight = {4, 5, 2};
int capacity = 9;
int[][] dp = new int[value.length+1][capacity+1];
for(int i=0; i<=value.length; i++) {
for(int j=0; j<=capacity; j++) {
if(i==0) {
dp[i][j] = 0;
} else {
if(weight[i-1] <= j){
dp[i][j] = Math.max(dp[i-1][j], value[i-1] + dp[i-1][j - weight[i-1] ]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
}
System.out.println("optimal value is: " + dp[value.length][capacity]);
}
This prints the optimal solution which is 9.
I now want to find what items make up the optimal solution (in this case it will be I1, I2).
The logic I am using is as follows:
The matrix dp[][] is as follows:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 5 5 5 5 5
0 0 0 0 5 5 5 5 5 9
0 0 3 3 5 5 8 8 8 9
Row 4 (index 3) in dp[][] corresponds to item 3 so I compare the dp[3][9] (bottom right corner) with dp[2][9]. Since both values are the same I know item 3 was not chosen. I go to dp[2][9].
I compare dp[2][9] to dp[1][9]. Since the values are different, I know item 2 was chosen. I go to dp[1][9 - weight of item 2] => dp[1][4].
I compare dp[1][4] with dp[0][4]. The values are different so I know item 1 was chosen. I go to dp[0][4 - weight of item 1] => dp[0][0].
dp[0][0] is the terminal state so I return.
The result from this operation is: [1, 1, 0] where 1 denotes item1, item2 were taken and 0 means item3 was not taken.
My question is:
How can I find the path (in this case picked items) when I optimize for space? Is it even possible?
For example instead of using a matrix, I can use 2 arrays and change the program as follows:
public static void main(String[] args) {
int[] value = {5, 4, 3};
int[] weight = {4, 5, 2};
int capacity = 9;
int[] row0 = new int[capacity+1];
int[] row1 = new int[capacity+1];
for(int i=0; i<=3; i++) {
for(int j=0; j<=capacity; j++) {
if(i==0) {
row1[j] = 0;
} else {
if(weight[i-1] <= j) {
row1[j] = Math.max(row0[j], value[i-1]+ row0[j-weight[i-1]]);
} else {
row1[j] = row0[j];
}
}
}
for(int j = 0; j< row0.length; j++)
row0[j] = row1[j];
}
System.out.println("optimal value is: " + row1[capacity]);
}
If I do this I will only have the last 2 rows at most which are:
row0 = { 0 0 0 0 5 5 5 5 5 9 }
row1 = { 0 0 3 3 5 5 8 8 8 9 }
How can I trace back the path with only this information?
There isn't a good solution for all DP problems.
For this problem, for example, I would keep a bitmask with each accessible sum that indicates which elements you selected to produce that sum. This works for knapsack, because the number of elements is small and the selection order doesn't matter.
For many other DP problems (LCS or shortest-path, for example) it works well to remember the paths as reverse-order linked lists. The lists share tails and usually the ones you have to remember have similar histories. Every so often you may have to scan the structure to make sure it's still compact. When you really have to, you can drop every Nth element, which will then require you to do a small search to connect each pair when you reconstruct the path.