CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice 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)).

Starter code

solution.py
def knap_items(W, weights, values, n):
    # Knapsack selection

Sample solution

solution.py
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))

Expected output

[2, 3]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Decision table: match the terms

Term Meaning
decision Decision
take Take
skip Skip
backtrack Backtrack

2 Which cell holds knapsack DP's result?

  • dp[n][W] Correct answer
  • dp[n][0]
  • dp[0][0]
  • dp[0][W]

Explanation: dp[n][W].

3 Take check

Question 
if dp[i][w] != dp[____][w]:
Answer 
if dp[i][w] != dp[i - 1][w]:

Explanation: i - 1 is right.

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4