CodeBlanks Logo Icon CodeBlanks
Login Register

Knapsack problem

Fill a capacity with weighted, valuable items.

Knapsack problem

Knapsack: given items with weight and value, fill the capacity without exceeding it to maximize value.

0/1 knapsack: each item is either taken or not; no splitting.

Knapsack is used in resource allocation and investment decisions; a classic DP problem.

0/1 vs fractional

In 0/1 knapsack an item is either taken or not. In fractional knapsack items can be split; greedy is optimal.

0/1 knapsack requires dynamic programming; greedy is not always optimal.

This distinction determines which method to apply; an important choice.

Practice Knapsack brute

Write knap_brute(W, weights, values, n). Recursive brute-force 0/1 knapsack. Print 220 with print(knap_brute(50, [10, 20, 30], [60, 100, 120], 3)).

Starter code

solution.py
def knap_brute(W, weights, values, n):
    # Knapsack brute

Sample solution

solution.py
def knap_brute(W, weights, values, n):
    # Knapsack brute
    if n == 0 or W == 0:
        return 0
    if weights[n - 1] > W:
        return knap_brute(W, weights, values, n - 1)
    take = values[n - 1] + knap_brute(W - weights[n - 1], weights, values, n - 1)
    skip = knap_brute(W, weights, values, n - 1)
    return max(take, skip)
print(knap_brute(50, [10, 20, 30], [60, 100, 120], 3))

Expected output

220

Questions and answers

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

1 How is each item handled in 0/1 knapsack?

  • Half taken
  • Split
  • Divided
  • Either taken or not Correct answer

Explanation: Either taken or not.

2 Capacity exceed

Question 
if w > ____:
Answer 
if w > capacity:

Explanation: capacity is right.

3 Knapsack problem: match the terms

Term Meaning
knapsack Knapsack
weight Weight
value Value
capacity Capacity

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