I have tried researching how I can handle multiple optimal solutions based using dynamic programming. The answer is found from this question is simply that you have to backtrack. What if this is not possible and one of my solutions can't be found this way?
From this YouTube video we are given the problem of finding the optimal rod cuttings for maximizing profit.
The rod has a length of $n=5$, and the possible ways to cut with its respective values in parenthesis are 1ドル(2)$, 2ドル(5)$, 3ドル(7)$ and 4ドル(8)$. By setting up a matrix as in the video we end up finding that the optimal solution is 12ドル$. By backtracking this we are only able to find one of the solutions 1,2,2ドル$ and not the other solution consisting of 2,3ドル$.
My question is, how can I combine dynamic programming with some sort of best sequence sum algorithm so that I am able to backtrack both solutions? The algorithm he proposes uses the max of the previous subproblem, however, that might not be the only solution as a combination of the current subproblem might also be feasible.
The matrix proposed in the video looks like this (rows are the possible cuts and columns are the rod length): $$ \begin{bmatrix} 0 & 2 & 4 & 6 & 8 & 10 \\ 0 & 2 & 5 & 7 & 10 & 12 \\ 0 & 2 & 5 & 7 & 10 & 12 \\ 0 & 2 & 5 & 7 & 10 & 12 \\ \end{bmatrix} $$
1 Answer 1
Assume you already computed the dynamic programming table DP[SIZE][LENGTH] where DP[s][l] stands for maximum profit that can be obtained by using cuts up to size s on a rod of length l. You want to find all decomposition to get the value DP[SIZE][LENGTH], to do this notice that at every step DP[s][l] we have two options, use the cut of size s or don't use it (possibly using both values we get optimal answer). The pseudo code will look like this:
PROFIT[s] = value of using a cut of size `s`.
def find_answers(s, l, partial_answer):
""" Populate in `partial_answer` possible ways to
partition a rod of length `l` using cuts of
size up to `s` and report them.
`partial_answer` is a multiset that will contain all cuts
done so far.
"""
# Base case when length is `0`.
if l == 0:
report partial_answer
best = DP[s][l]
# If not using the cut of size `s` gets a profit as good
# as best expected profit, find solutions.
if DP[s - 1][l] == best:
find_answers(s - 1, l, partial_answer)
# Try to find an answer that uses current cut size if `s` is
# less than current length, and profit using this cut is as good
# as best expected profit.
if s <= l and DP[s][l - s] + PROFIT[s] == best:
find_answers(s, l - s, partial_answer + {s})
Call this function like find_answers(SIZE, LENGTH, {}) with an empty multi-set as partial_answer. Since it is doing backtracking it is possible to get to the same state (s, l) several times with different partial_answers. This function will call report partial_answer exactly once per valid decomposition, also notice that the number of optimal decomposition can be exponentially large.