# Knapsack Problem: Find Top-K Lower Profit Solutions

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?

## 1 Answer

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.