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.

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

Show example solution

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

Test yourself

How is each item handled in 0/1 knapsack?
- Half taken
- Split
- Divided
- Either taken or not
Show answer

Either taken or not — Either taken or not.
Capacity exceed
```
if w > ____:
```
Show answer
```
if w > capacity:
```
Knapsack problem: match the terms

knapsack

Knapsack
weight

Weight
value

Value
capacity

Capacity

Next lesson: 0/1 knapsack DP

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies