Decision table

Take-or-skip decision fills the table.

Decision table

The DP table stores a 'take' or 'skip' decision for each item. The result dp[n][W] holds the maximum value.

The table can also reveal which items are selected; backtracking is used.

So knapsack DP stores not just the value but the decisions too.

Item selection

Backtracking reveals which items were taken: if dp[i][w] ≠ dp[i-1][w] then item i was taken.

This gives not just the max value but which items produced it.

In practice, it shows which assets to pick in investment decisions.

Exercise Knapsack selection

Write knap_items(W, weights, values, n). Use DP + backtracking to return taken item indices. Print [2, 3] with print(knap_items(50, [10, 20, 30], [60, 100, 120], 3)).

Show example solution

def knap_items(W, weights, values, n):
    # Knapsack selection
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    items = []
    i, w = n, W
    while i > 0 and w > 0:
        if dp[i][w] != dp[i - 1][w]:
            items.append(i)
            w -= weights[i - 1]
        i -= 1
    return sorted(items)
print(knap_items(50, [10, 20, 30], [60, 100, 120], 3))

Test yourself

Decision table: match the terms

decision

Decision
take

Take
skip

Skip
backtrack

Backtrack
Which cell holds knapsack DP's result?
- dp[n][W]
- dp[n][0]
- dp[0][0]
- dp[0][W]
Show answer

dp[n][W] — dp[n][W].

Take check

if dp[i][w] != dp[____][w]:

Show answer

if dp[i][w] != dp[i - 1][w]:

Next lesson: Summary - Knapsack

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies