Teaching Transcript: 0/1 Knapsack Problem Using Dynamic

Programming

Hello and welcome to today’s session! Today, we’re diving into the "0/1 Knapsack Problem,"
a classic optimization problem that showcases the power of dynamic programming. This
problem is a fantastic way to learn how to break down complex decisions into smaller
subproblems, making it easier to find the optimal solution. By the end of this session, you’ll
understand how to maximize value within constraints, a concept that applies to real-world
scenarios like resource allocation or project selection. Let’s get started with the problem
statement and explore this exciting challenge together!

Problem Statement

The 0/1 Knapsack Problem involves selecting items to include in a knapsack with a limited
weight capacity to maximize the total value. You’re given:

● An array of n items, where each item i has a weight weights[i] and a value values[i].
● A knapsack with a maximum weight capacity W.
● Each item can either be included (1) or excluded (0), but you can’t take a fraction of
an item.

Your task is to select a subset of items that fits within the weight capacity W and maximizes
the total value. For example, consider:

● Items: weights = [1, 2, 3, 4, 5, 6], values = [10, 20, 30, 40, 50, 60], capacity W = 12.
● You need to choose items such that their total weight is at most 12 and their total
value is maximized.

The goal is to find the maximum possible value. Any questions about the problem statement
before we move forward?

Building Intuition

The 0/1 Knapsack Problem is about making choices under constraints. For each item, we
decide whether to include it or not, but we must ensure the total weight doesn’t exceed the
knapsack’s capacity. The “0/1” part means we can’t split items—they’re either fully included
or not included at all. The key insight is that each decision affects future choices because
including an item reduces the remaining capacity.

Imagine you’re packing a backpack for a hike with a weight limit. You have items like a water
bottle, snacks, and a camera, each with a weight and a “value” (how useful it is). You want to
maximize the usefulness of what you carry without overloading the backpack. To make
optimal choices, we need to consider all possible combinations of items, but checking every
subset would be too slow. Instead, we can use dynamic programming to build solutions
incrementally by considering each item and possible knapsack capacities, avoiding
redundant calculations.
Discussing Possible Approaches

Let’s explore a couple of ways to solve this:

1. Naive Approach: Brute Force

We could try every possible subset of items and calculate the total value and weight
for each, keeping only those subsets whose weight is at most W, and then pick the
one with the maximum value. With n items, there are 2^n subsets, and checking
each takes O(1) time for weight and value calculations. This gives a time complexity
of O(2^n), which is exponential and impractical for large n (e.g., n > 30).
2. Dynamic Programming Approach
A more efficient approach uses dynamic programming to avoid recalculating the
same subproblems. We can define a memoizedTable table where each cell
represents the maximum value achievable with a subset of the first i items and a
knapsack capacity of w. By building this table iteratively, we consider whether to
include each item or not, based on whether it improves the total value while staying
within the weight limit. This approach is optimal, with a time complexity of O(n*W),
which is pseudo-polynomial but much faster than brute force for practical inputs.

The memoizedTable approach is the standard solution because it systematically explores all
relevant choices while reusing solutions to subproblems, making it efficient for typical input
sizes. Let’s dive into the details of this approach.

Detailed Explanation of the Optimal Approach (Dynamic Programming)

The dynamic programming approach works as follows:

1. Define the memoizedTable Table: Create a 2D table memoizedTable[i][w] where

memoizedTable[i][w] represents the maximum value achievable using the first i items
(indices 0 to i-1) with a knapsack capacity of w (from 0 to W).
2. Base Case: When no items are considered (i = 0) or the capacity is 0 (w = 0), the
maximum value is 0, so memoizedTable[0][w] = 0 and memoizedTable[i][0] = 0.
3. Fill the Table: For each item i (1 to n) and capacity w (1 to W):
○ If the current item’s weight (weights[i-1]) is greater than w, we can’t include it,
so memoizedTable[i][w] = memoizedTable[i-1][w] (same as without this item).
○ Otherwise, we choose the maximum of:
■ Excluding the item: memoizedTable[i-1][w].
■ Including the item: values[i-1] + memoizedTable[i-1][w - weights[i-1]]
(item’s value plus the maximum value for the remaining capacity).
4. Result: The value in memoizedTable[n][W] is the maximum value achievable with all
n items and capacity W.

This approach is efficient because it solves each subproblem once and stores the results in
the memoizedTable table, avoiding the exponential cost of brute force.

Language-Independent Pseudocode

Here’s the pseudocode for the memoizedTable approach:

0/1 Knapsack Problem memoizedTable Pseudocode:

unction knapsack(weights, values, W): // Initialize memoizedTable table n =
LENGTH(weights) memoizedTable = CREATE_2D_ARRAY(n + 1, W + 1)

// Base case: no items or zero capacity

FOR i FROM 0 TO n:
memoizedTable[i][0] = 0
FOR w FROM 0 TO W:
memoizedTable[0][w] = 0

// Fill memoizedTable table

FOR i FROM 1 TO n:
FOR w FROM 1 TO W:
IF weights[i-1] <= w:
// Choose max of including or excluding item
memoizedTable[i][w] = MAX(memoizedTable[i-1][w], values[i-1] + memoizedTable[i-
1][w - weights[i-1]])
ELSE:
// Can't include item
memoizedTable[i][w] = memoizedTable[i-1][w]

// Return maximum value

RETURN memoizedTable[n][W]

Explanation of Pseudocode

● The memoizedTable table has dimensions (n+1) × (W+1) to include base cases.
● We initialize the first row (i=0) and first column (w=0) to 0, as no value is possible
with no items or no capacity.
● For each item i and capacity w, we check if the item’s weight fits. If it does, we take
the maximum of including the item (adding its value and using the remaining
capacity) or excluding it (using the previous row’s value). If it doesn’t fit, we exclude
the item.
● The final answer is in memoizedTable[n][W], representing the maximum value for all
items and capacity W.

Visualization in Frames

Let’s visualize the process using the example:

● weights = [1, 2, 3, 4, 5, 6], values = [10, 20, 30, 40, 50, 60], W = 12.
Imagine a 2D table where rows represent items (0 to 6) and columns represent
capacities (0 to 12). Each frame shows the table being filled for a specific item.

Initialize the memoizedTable Table

 ● Text: “Initialize memoizedTable[0][w] = 0 and memoizedTable[i][0] = 0 for base
cases.”
● Action: Set the first row and column to 0.

i\w | 0 1 2 3 4 5 6 7 8 9 10 11 12
----+--------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0
2 | 0
3 | 0
4 | 0
5 | 0

6 | 0

Process Item 1 (weight=1, value=10)

● “For i=1, w=1 to 12: weight=1 fits, so memoizedTable[1][w] = max(memoizedTable[0]

[w], 10 + memoizedTable[0][w-1]).”
● Fill row 1. E.g., for w=1: max(0, 10 + memoizedTable[0][0]) = 10; for w=2: max(0, 10
+ memoizedTable[0][1]) = 10.

Visualization:

i\w | 0 1 2 3 4 5 6 7 8 9 10 11 12
----+--------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0 10 10 10 10 10 10 10 10 10 10 10 10
2 | 0
3 | 0
4 | 0
5 | 0

6 | 0

Process Item 2 (weight=2, value=20)

● Text: “For i=2, w=1: weight=2 doesn’t fit, memoizedTable[2][1] = memoizedTable[1]

[1]. For w=2 to 12: weight=2 fits, memoizedTable[2][w] = max(memoizedTable[1][w],
20 + memoizedTable[1][w-2]).”
● Action: Fill row 2. E.g., for w=2: max(10, 20 + memoizedTable[1][0]) = 20; for w=3:
max(10, 20 + memoizedTable[1][1]) = 30.

Visualization:

i\w | 0 1 2 3 4 5 6 7 8 9 10 11 12
----+--------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0 10 10 10 10 10 10 10 10 10 10 10 10
2 | 0 10 20 30 30 30 30 30 30 30 30 30 30
3 | 0
4 | 0
5 | 0

6 | 0

Process Item 3 (weight=3, value=30)

● “For i=3, w=1 to 2: weight=3 doesn’t fit. For w=3 to 12: weight=3 fits,
memoizedTable[3][w] = max(memoizedTable[2][w], 30 + memoizedTable[2][w-3]).”
● Fill row 3. E.g., for w=3: max(30, 30 + memoizedTable[2][0]) = 30; for w=4: max(30,
30 + memoizedTable[2][1]) = 40.

Visualization:

i\w | 0 1 2 3 4 5 6 7 8 9 10 11 12
----+--------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0 10 10 10 10 10 10 10 10 10 10 10 10
2 | 0 10 20 30 30 30 30 30 30 30 30 30 30
3 | 0 10 20 30 40 50 60 60 60 60 60 60 60
4 | 0
5 | 0

6 | 0

Process Item 4 (weight=4, value=40)

● Text: “For i=4, w=1 to 3: weight=4 doesn’t fit. For w=4 to 12: weight=4 fits,
memoizedTable[4][w] = max(memoizedTable[3][w], 40 + memoizedTable[3][w-4]).”
● Action: Fill row 4. E.g., for w=4: max(40, 40 + memoizedTable[3][0]) = 40; for w=5:
max(50, 40 + memoizedTable[3][1]) = 50.

Visualization:

i\w | 0 1 2 3 4 5 6 7 8 9 10 11 12
----+--------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0 10 10 10 10 10 10 10 10 10 10 10 10
2 | 0 10 20 30 30 30 30 30 30 30 30 30 30
3 | 0 10 20 30 40 50 60 60 60 60 60 60 60
4 | 0 10 20 30 40 50 60 70 80 80 80 80 80
5 | 0

6 | 0
Process Item 5 (weight=5, value=50)

● “For i=5, w=1 to 4: weight=5 doesn’t fit. For w=5 to 12: weight=5 fits,
memoizedTable[5][w] = max(memoizedTable[4][w], 50 + memoizedTable[4][w-5]).”
● Fill row 5. E.g., for w=5: max(50, 50 + memoizedTable[4][0]) = 50; for w=6: max(60,
50 + memoizedTable[4][1]) = 60.

Visualization:

i\w | 0 1 2 3 4 5 6 7 8 9 10 11 12
----+--------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0 10 10 10 10 10 10 10 10 10 10 10 10
2 | 0 10 20 30 30 30 30 30 30 30 30 30 30
3 | 0 10 20 30 40 50 60 60 60 60 60 60 60
4 | 0 10 20 30 40 50 60 70 80 80 80 80 80
5 | 0 10 20 30 40 50 60 70 80 90 90 90 90

6 | 0

: Process Item 6 (weight=6, value=60)

● “For i=6, w=1 to 5: weight=6 doesn’t fit. For w=6 to 12: weight=6 fits,
memoizedTable[6][w] = max(memoizedTable[5][w], 60 + memoizedTable[5][w-6]).”
● Fill row 6. E.g., for w=6: max(60, 60 + memoizedTable[5][0]) = 60; for w=12: max(90,
60 + memoizedTable[5][6]) = 120.

Visualization:

i\w | 0 1 2 3 4 5 6 7 8 9 10 11 12
----+--------------------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0 10 10 10 10 10 10 10 10 10 10 10 10
2 | 0 10 20 30 30 30 30 30 30 30 30 30 30
3 | 0 10 20 30 40 50 60 60 60 60 60 60 60
4 | 0 10 20 30 40 50 60 70 80 80 80 80 80
5 | 0 10 20 30 40 50 60 70 80 90 90 90 90

6 | 0 10 20 30 40 50 60 70 80 90 100 110 120

Final result : The table is complete! The maximum value is memoizedTable[6][12],

which is 120, shown in the bottom-right cell. To find the items, trace back from
memoizedTable[6][12]. At w equals 12, memoizedTable[6][12] equals 120 comes from
including item 6 (value 60) plus memoizedTable[5][6], which is 60. So, item 6 is
included, reducing capacity to 6. At memoizedTable[5][6], we include item 3 (weight 3,
value 30) since memoizedTable[5][6] equals 60 comes from 30 plus memoizedTable[4]
[3]. This uses weight 6 plus 3 equals 9, with value 60 plus 30 equals 90. The optimal
combination might include items like 3 and 6, but memoizedTable[6][12] equals 120
suggests a better set, possibly items 1, 2, and 6 (weights 1 plus 2 plus 6 equals 9,
values 10 plus 20 plus 60 equals 90) or others summing to 120. The table confirms the
maximum value is 120.

Time and Space Complexity

● Time Complexity:
○ The memoizedTable table has dimensions (n+1) × (W+1).
○ Filling each cell takes O(1) time (max operation and array access).
○ Total: O(n*W), where n is the number of items and W is the capacity.
○ This is pseudo-polynomial, as it depends on the numerical value of W.
● Space Complexity:
○ The memoizedTable table uses O(n*W) space for (n+1) × (W+1) cells.
○ Other variables (e.g., loop counters) use O(1).
○ Total: O(n*W).
○ Note: This can be optimized to O(W) using a 1D array, but the 2D approach is
clearer for teaching.

The dynamic programming approach to the 0/1 Knapsack Problem efficiently maximizes
value by breaking the problem into subproblems stored in a memoizedTable table. The time
complexity of O(nW) is a vast improvement over the O(2^n) brute force approach, making it
practical for reasonable n and W. The space complexity of O(nW) supports the table’s
storage needs. The visualization with our six-item example shows how the table builds the
solution step by step. That’s all for today’s problem-solving session—thanks for learning with
me today .