In-Class Lecture 17

The questions below are due on Monday November 09, 2026; 11:59:00 PM.
 
You are not logged in.

Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

Download Materials

What You'll Learn Here
  • How to represent a 0/1 knapsack problem in code.
  • How exhaustive enumeration uses the power set to find an optimal solution.
  • How to define a recursive knapsack subproblem precisely.
  • How include/exclude decisions change the remaining capacity.
  • How to prune an include branch when its item does not fit.
  • How an index can represent the remaining items without repeatedly slicing a list.

1) Represent the Problem

We will solve the 0/1 knapsack problem: choose a subset of items with the greatest possible total value without exceeding a weight capacity. The name 0/1 means that each item has exactly two possibilities: take none of it or take the whole item.

Represent each item with a tuple in the order (name, value, weight). Our running example is:

ItemValueWeight
gold2505
saffron2404
diamond15003

items = [
    ("gold", 250, 5),
    ("saffron", 240, 4),
    ("diamond", 1500, 3),
]
capacity = 10

The three items weigh 12 in total, so we cannot take all of them. Gold and diamond have a total weight of 8 and a total value of 1750, which is better than saffron and diamond at value 1740. This is the result our algorithms should reproduce.

The lecture code uses small helper functions:

def item_names(items):
    return [item[0] for item in items]

def total_value(items):
    return sum([item[1] for item in items])

def total_weight(items):
    return sum([item[2] for item in items])

Question 1: Consider the selection below and a capacity of 4.

selection = [
    ("laptop", 900, 4),
    ("charger", 80, 1),
]

Which statements are true? Check all that apply.

item_names(selection) returns ["laptop", "charger"].
total_value(selection) returns 980.
total_weight(selection) returns 4.
The selection is infeasible because its total weight exceeds the capacity.

2) First Approach: Enumerate Every Subset

Our first exact solution reuses powerset from the previous lecture. It follows three steps:

  1. Generate every possible selection.
  2. Ignore selections whose total weight exceeds the capacity.
  3. Among the valid selections, keep the one with the greatest total value.

def knapsack_enumerate(items, capacity):
    best_candidate = None
    best_value = 0

    for selection in powerset(items):
        if total_weight(selection) <= capacity:
            value = total_value(selection)
            if value > best_value:
                best_candidate = item_names(selection)
                best_value = value

    return best_candidate, best_value

The outer loop considers every candidate, the first if enforces feasibility, and the second if performs the optimization. Keeping these two checks separate is important because a high-value selection is not a candidate at all if it exceeds the capacity.

For the running example, the function returns the names ["gold", "diamond"] and value 1750. Because it checks every possible selection, no valid selection with a greater value can have been missed.

Question 2: Suppose knapsack_enumerate has already found a valid selection worth 900, so best_value == 900. It next encounters these candidates in order:
  1. Candidate A has total weight 7 and total value 1100.
  2. Candidate B has total weight 6 and total value 950.

The capacity is 6. What happens?

Candidate A is rejected even though its value is greater than 900; Candidate B then becomes the new best candidate.
Candidate A becomes the new best candidate because 1100 is the largest value.
Candidate B is rejected because its value is lower than Candidate A's value.
Neither candidate changes the answer because the algorithm keeps the first valid selection it finds.

The exhaustive solution is simple and correct, but it generates all 2 ** n subsets. It even constructs selections that are already too heavy and will immediately be rejected. Timing increasingly large random problems makes this exponential growth visible: adding one item doubles the number of possible selections.

3) Define the Recursive Subproblem

This idea solves the decision tree one subproblem at a time.

  • knapsack_decision_tree(items, capacity) returns a tuple (solution, value) containing the most valuable selection that can be made from items without exceeding capacity.

Here is the recursive code. Explanations of each part of the code is below.

def knapsack_decision_tree(items, capacity):
    # base case: no remaining items means an empty solution.
    if len(items) == 0:
        return [], 0

    # separate the current item from the remaining items.
    item, remaining = items[0], items[1:]
    name, value, weight = item

    # branch 1: do not take the current item.
    sol_without, val_without = knapsack_decision_tree(
        remaining, capacity
    )

    # branch 2: take the current item, if it fits.
    if weight <= capacity:
        sol_with, val_with = knapsack_decision_tree(
            remaining, capacity - weight
        )
        sol_with.append(name)
        val_with += value
    else:
        sol_with, val_with = [], 0

    # return the better of the two branches.
    if val_with > val_without:
        return sol_with, val_with
    return sol_without, val_without

In this idea, one recursive call does not only choose the next item; it returns the best answer from an entire subtree of later choices.

If there are no items left, the only possible selection is empty, with value zero:

if len(items) == 0:
    return [], 0

For a nonempty input, separate the first item from the remaining items and unpack its three fields:

item, remaining = items[0], items[1:]
name, value, weight = item

The decision tree now has two branches. If we leave the item out, the remaining capacity does not change:

sol_without, val_without = knapsack_decision_tree(
    remaining, capacity
)

If we take the item, its weight must fit. The recursive call receives the reduced capacity; when it returns the best solution for the remaining items, we add the current item's name and value:

if weight <= capacity:
    sol_with, val_with = knapsack_decision_tree(
        remaining, capacity - weight
    )
    sol_with.append(name)
    val_with += value

For the initial gold decision, the exclude branch solves ([saffron, diamond], 10), while the include branch solves ([saffron, diamond], 5) and then adds gold. The item list changes in both branches, but only the include branch changes the capacity.

Question 3: Consider this knapsack problem:

items = [
    ("gold", 250, 5),
    ("saffron", 240, 4),
    ("diamond", 1500, 3),
]
capacity = 10

Which recursive calls correctly represent the decision about gold? Check all that apply.

Exclude gold: solve the saffron-and-diamond subproblem with capacity 10.
Include gold: solve the saffron-and-diamond subproblem with capacity 5, then add gold and its value.
Exclude gold: solve the original three-item problem with capacity 5.
Include gold: solve the saffron-and-diamond subproblem with capacity 10 because gold has already been selected.

4) Prune Infeasible Branches and Choose the Better Answer

Suppose only 1 unit of capacity remains when we consider the 3-unit diamond. The include branch cannot possibly lead to a valid selection. Instead of entering that branch and eventually discovering a negative capacity, we stop it immediately:

if weight <= capacity:
    sol_with, val_with = knapsack_decision_tree(
        remaining, capacity - weight
    )
    sol_with.append(name)
    val_with += value
else:
    sol_with = []
    val_with = 0

This is the pruning step. In a larger tree, skipping one infeasible decision can avoid exploring an entire subtree. The exclude branch is always feasible because leaving an item out consumes no capacity.

After solving the feasible branches, the current call returns only the better of their two answers:

if val_with > val_without:
    return sol_with, val_with
else:
    return sol_without, val_without

This differs from powerset. A power-set call combines and returns every result from both branches. A knapsack call compares the best result from each branch and returns only the more valuable one.

Code Question 1: The solver below produces the correct items, but append places their names in reverse input order as the recursive calls return. Modify the function so that selected names appear in the same order as they appeared in items.

Do not call reverse() or sort(), and do not mutate the list returned by the recursive call. The selected items and total value should remain unchanged.

Pruning improves the running time when many items do not fit, but the worst case is still exponential. If every remaining item fits at every node, the algorithm still explores both branches.

Question 4: Trace this call:

knapsack_decision_tree([ ("book", 40, 3), ("camera", 100, 5), ], 4)

Which statements are true? Check all that apply.

The camera's include branch is pruned when it is considered with capacity 4.
After including the book, the camera is considered with capacity 1 and its include branch is pruned.
The function returns (["camera"], 100) because the camera has the greater value.
The function returns (["book"], 40).
The function returns both valid selections so that its caller can compare them.

5) Represent Remaining Items with an Index

The first recursive solver passes items[1:] into each child. We can describe the same subproblem without creating a new list slice. We keep the original list fixed and use an index to mark the first item that has not yet been considered.

  • indexed_helper(items, index, capacity) returns the best selection using items from index onward that fits within capacity.

The public function starts at index 0. Each decision advances to index + 1, and the base case occurs when the index reaches the length of the list:

def knapsack_indexed(items, capacity):
    return indexed_helper(items, 0, capacity)

def indexed_helper(items, index, capacity):
    if index == len(items):
        return [], 0

    name, value, weight = items[index]

    sol_without, val_without = indexed_helper(
        items, index + 1, capacity
    )

    if weight <= capacity:
        sol_with, val_with = indexed_helper(
            items, index + 1, capacity - weight
        )
        sol_with.append(name)
        val_with += value
    else:
        sol_with, val_with = [], 0

    if val_with > val_without:
        return sol_with, val_with
    return sol_without, val_without

The algorithmic decisions have not changed. Slicing version (remaining_items, capacity) and indexed version (index, capacity) are two representations of the same subproblem. The indexed form makes it especially clear when two branches ask the same question. If both reach the same index and capacity, everything below them is identical.

Question 5: Use the running list [gold, saffron, diamond]. Suppose the indexed solver reaches:

indexed_helper(items, 1, 5)

Which statements correctly trace this state? Check all that apply.

The next item being considered is saffron.
The exclude branch calls indexed_helper(items, 2, 5).
The include branch calls indexed_helper(items, 2, 1).
The include branch calls indexed_helper(items, 1, 1) because the solver is still processing saffron.
This state is a base case because only two items remain.

6) Memoize Fibonacci

The ordinary recursive Fibonacci function repeats work:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

For example, evaluating fib(5) reaches fib(3) through more than one branch. Because every call with the same n has the same answer, we can store each answer after computing it and reuse it later.

Code Question 2: Rewrite the Fibonacci calculation to use memoization. fib should create one empty memo for the calculation. fib_helper should return a saved answer when possible and save each newly computed answer before returning it.

7) Memoize Knapsack

Question 7: Memoize Knapsack. The editor contains a working indexed knapsack solver without memoization. Modify it to use an explicit dictionary, following the Fibonacci example above; do not use @cache.
  1. Create a fresh memo = {} inside knapsack_indexed.
  2. Add a memo parameter to indexed_helper and pass the same dictionary to every recursive call.
  3. Use (index, capacity) as the key. Return a saved answer when present, and store each newly computed non-base-case answer before returning it.
  4. Do not mutate a cached solution list. Replace sol_with.append(name) with an expression that creates a new list, such as sol_with = sol_with + [name].

Keep the return format (list_of_names, total_value), keep names in the starter code's reverse input order, and exclude the current item when the two branches tie. Assume nonnegative integer weights and capacity. Zero-weight items are allowed, so zero capacity is not necessarily a base case.

Click Run Code to execute the sample calls and see their printed output. The starting code already returns the correct answers; memoization should preserve them while avoiding repeated work. Edit the samples or add your own print calls to experiment. Click Submit to check answers and memo behavior against the provided tests. Tests that pass a memo to the helper will work after you add its new parameter.

Takeaways
  • A knapsack item is represented by its name, value, and weight.
  • Exhaustive enumeration is exact because it checks every subset, but it requires exponential work.
  • A recursive call returns the single best solution for its remaining items and capacity.
  • Excluding an item preserves capacity; including it reduces capacity by its weight.
  • If an item is too heavy, its include branch is infeasible and can be pruned.
  • Using an index changes the representation of the subproblem, not the decisions or result.



We forget 40% of new information within an hour of learning it, and 70% within a day. To combat the forgetting curve, use this box to comment or reflect on the content of this lecture (one way to earn participation!). Post lingering questions, an aha moment, something confusing/interesting/funny/surprising, etc.