Dynamic Programming: 0/1 Knapsack - Retrieving Combinations as array

Question

I've been studying Dynamic Programming from both a bottom-up iterative approach and a top-down recursive approach using memoization.

I've been tasked with solving the 0/1 Knapsack Problem and have successfully used the bottom-up approach but am unable to use the top-down approach.

Using information from a webpage(http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2017%20-%20Knapsack%20Problem%20and%20Memory%20Function.htm) I have come up with the following pseudocode which successfully computes the Value of the optimal solution. My issue is I cannot think of a way to keep track of the correct combination of the items which constitute this solution.

// values array containing the "profits" of each item
// weights array containing the "weight" of each item
// memo_pad is a list used to memoize recursive results
values[], weights[], memo_pad[]

knapsack_memoized(i, w):
    // i is the current item
    // w is the remaining weight allowed in the knapsack

    if memo_pad[i][w] < 0: // if value not memoized
        if w < weights[i]:
            memo_pad[i][w] = knapsack_memoized(i-1, w)
        else:
            memo_pad[i][w] = max{knapsack_memoized(i-1,w), values[i]+knapsack_memoized(i-1, w-weights[i])}

    return memo_pad[i][w]
end

I cannot figure out how to find out what combination of the input items will give me the returned optimised value?

Answer 1

you are looking to return the maximum of two cases: (1) nth item included (2) item not included

try this...

else:
    memo_pad[i][w] = max{values[i] + memo_pad[i-1][w-weights[i]], 
    memo_pad[i-1][w]}