Problem Set 18: The Knapsack Problem

Introduction — The Story

Imagine you are going on a hiking trip. You have a backpack (a knapsack) that can only carry so much weight. You also have a set of items: food, water bottles, a flashlight, a blanket, and so on.

• Each item has a weight (how heavy it is).
• Each item has a value (how useful it is to you).
• The goal: pack the backpack to maximize total usefulness (value) without going over the weight limit.

This is the Knapsack Problem — one of the most famous problems in computer science. It forces us to make smart choices under limited resources, which is exactly what computers, businesses, and people must do in real life.

Examples of real-life knapsack-like problems:

• Picking which apps to install on a phone with limited storage.
• Choosing which ads to show in limited slots on a website.
• Packing supplies for a space mission where weight is critical.

---

Two Versions

1. 0/1 Knapsack – You can either take an item or leave it (can’t take duplicates).
   Example: You can’t take two flashlights.
2. Unbounded Knapsack – You can take as many of each item as you want.
   Example: You can pack multiple bottles of water.

---

Problem Statement

You are given:

• capacity: maximum weight the backpack can hold.
• weights: list of weights for each item.
• values: list of values (usefulness) for each item.

Your job:

1. Write a function knapsack_01 to solve the 0/1 problem.
2. Write a function unbounded_knapsack for the unlimited-items version.
3. Return the maximum value (and in the 0/1 case, which items were chosen).

---

Starter Code

from typing import List, Tuple

def knapsack_01(capacity: int, weights: List[int], values: List[int]) -> Tuple[int, List[int]]:
    """
    0/1 Knapsack: choose items to maximize value without exceeding capacity.
    Each item can be taken at most once.
    Returns (max_value, chosen_indices_sorted).
    """
    n = len(weights)
    if capacity <= 0 or n == 0:
        return 0, []

    # dp[i][w] = max value using first i items, capacity w
    dp = [[0]*(capacity+1) for _ in range(n+1)]

    # Fill the DP table
    for i in range(1, n+1):
        wt, val = weights[i-1], values[i-1]
        for w in range(capacity+1):
            dp[i][w] = dp[i-1][w]  # don’t take item
            if wt <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w-wt] + val)  # take item

    max_value = dp[n][capacity]

    # Trace back to see which items were chosen
    chosen = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            chosen.append(i-1)
            w -= weights[i-1]
    chosen.reverse()
    return max_value, chosen


def unbounded_knapsack(capacity: int, weights: List[int], values: List[int]) -> int:
    """
    Unbounded Knapsack: choose items (any number of each).
    Returns max_value only.
    """
    n = len(weights)
    if capacity <= 0 or n == 0:
        return 0

    dp = [0]*(capacity+1)
    for i in range(n):
        wt, val = weights[i], values[i]
        for w in range(wt, capacity+1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]

---

Test Cases

from knapsack import knapsack_01, unbounded_knapsack

# 0/1 Knapsack
print(knapsack_01(5, [2, 2, 6, 5, 4], [6, 3, 5, 4, 6]))
# Expected: (9, [0, 1]) because taking item 0 (weight=2, value=6) and item 1 (weight=2, value=3) gives total 9

print(knapsack_01(7, [3, 4, 5], [30, 50, 60]))
# Expected: (80, [0, 1]) because 3+4=7 exactly, value=30+50=80

# Unbounded Knapsack
print(unbounded_knapsack(7, [2, 3, 4], [5, 7, 9]))
# Expected: 17 (take items of weight 2, 2, and 3 → value = 5+5+7 = 17)

print(unbounded_knapsack(10, [5, 3, 4], [10, 7, 8]))
# Expected: 22 (take 4+3+3 → value = 8+7+7 = 22)

 

Student Tasks

1. Fill in the knapsack_01 and unbounded_knapsack functions.
2. Run the test cases and confirm the outputs.
3. Try adding your own test case with different weights, values, and capacities.
4. Challenge: Modify the 0/1 version to print all possible optimal solutions.