1
$\begingroup$

In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table":

def knapsack(weights, values, capacity, n):
    n = len(weights)
    weights = np.concatenate(([0], weights))  # Prepend a zero
    values = np.concatenate(([0], values))    # Prepend a zero
    
    table = np.zeros((n+1, capacity+1), dtype=np.int64)  # The first row/column are zeros
    for i in range(n+1):
        for w in range(capacity+1):
            if i == 0 or w == 0:
                table[i, w] = 0
            elif weights[i] <= w:
                table[i, w] = max(
                    table[i-1, w-weights[i]] + values[i],
                    table[i-1, w]
                )
            else:
                table[i, w] = table[i-1, w]
    return table

Then, by traversing the table using the following code, I am then able identify the items that make up the optimal solution:

def get_items(weights, capacity, table):
    items = []
    i = len(weights)
    j = capacity
    weights = np.concatenate(([0], weights))  # Prepend a zero
    table_copy = table.copy()
    while i > 0 and j > 0:
        if table_copy[i, j] == table_copy[i-1, j]:
            pass  # Item is excluded
        else:
            items.append(i-1)  # Item is included, fix shifted index due to prepending zero
            j = j - weights[i]
        i = i-1
    return items

This is great for finding the items that make up the single optimal solution (i.e., highest total summed value). However, I can't seem to figure out how to retrieve, say, the top-3 or top-5 solutions from this table that has a total weight that is less than or equal to the maximum capacity.

For example, the top-3 solutions for the following input would be:

weights = [1,  2,  3, 2, 2]
values =  [6, 10, 12, 6, 5]
capacity = 5

# with corresponding "dp table"
array([[ 0,  0,  0,  0,  0,  0],
       [ 0,  6,  6,  6,  6,  6],
       [ 0,  6, 10, 16, 16, 16],
       [ 0,  6, 10, 16, 18, 22],
       [ 0,  6, 10, 16, 18, 22]])
Total Summed Value Items (Zero-based Index)
22 1, 2
22 0, 1, 3
21 0, 1, 4

Note that there is a tie for both first place and so we'd truncate the solutions after the first 3 rows (though, getting all ties is preferred if possible). Is there an efficient way to obtain the top-k solutions from the "dp table" via some sort of backtracking process?

$\endgroup$

1 Answer 1

0
$\begingroup$

Dynamic programming algorithms can often be viewed as a shortest-paths problem on a suitable dag. Then, if you only want the top-1 solution, i.e., the shortest path, you can use prev pointers to find the shortest path. If you want the top-$k$ solutions, you can use any algorithm for finding the $k$ shortest paths in a graph. See, e.g., https://en.wikipedia.org/wiki/K_shortest_path_routing, https://en.wikipedia.org/wiki/Yen%27s_algorithm, https://stackoverflow.com/q/7208720/781723.

In your code, you have

table[i, w] = max(
                    table[i-1, w-weights[i]] + values[i],
                    table[i-1, w]
                )

You can think of this as corresponding to a dag where each pair $(i,w)$ corresponds to a vertex in the dag, and I suspect the above expression means that you have an edge from $(i-1,w)$ to $(i,w)$ of length 0 and an edge from $(i-1,w-\text{weights}[i])$ to $(i,w)$ of length $-\text{values}[i]$. (Why negation? To convert the "max" to a "min".) I'll let you work out the details of how your algorithm can be expressed as a problem of finding a shortest path in a dag.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.