Advanced Algorithms (Winter 2026-27) - 03-02 Knapsack

Overview

Knapsack selects a subset of n items with given weights and values, keeping total weight at most capacity B while maximizing total value; the problem is NP-hard. A dynamic program can track the best value using the first i items and capacity b, yielding about nB subproblems, which is pseudo-polynomial because B can be exponential in its binary encoding length.

Key takeaways

Knapsack maximizes the total value of a selected item subset subject to a total-weight limit B.
A compact dynamic programming state uses the first i items and a capacity limit b, avoiding a separate state for every subset.
The table contains about nB states, with each item considered for inclusion or exclusion when building the recurrence.
Because B takes about log B bits to encode, nB can be exponential in the input length even though it is polynomial in the numeric value B.
Pseudo-polynomial algorithms commonly arise when a dynamic programming table dimension is bounded by an input number rather than by that number’s encoding length.

Chapters

0:00 Knapsack’s Capacity Constraint and NP-Hardness

Each of n items has a weight and a value, and the goal is to maximize the value of a subset whose total weight is at most capacity B.
Knapsack is NP-hard, though its numeric inputs allow a pseudo-polynomial algorithm when the relevant numbers are small.
A reduction proving hardness would need to encode difficult instances using numeric values, since small numbers can be handled efficiently.

2:25 Dynamic Programming Over Item Prefixes and Capacity

Instead of creating a subproblem for every subset, restrict each subproblem to the first i items and capacity b.
Define each table entry as the best value obtainable from the first i items while using at most b capacity.
For the next item, consider two choices: include it or leave it out, then derive the best value from the corresponding smaller subproblems.

4:47 Why the Knapsack Table Is Pseudo-Polynomial

The table has roughly nB states, since i ranges over the n items and b ranges over capacities up to B.
The item count n is bounded by the input length, but capacity B is represented using only about log B bits.
B can therefore be exponential in the input’s encoding length, making the algorithm pseudo-polynomial rather than polynomial in input size.
The pseudo-polynomial feature comes from a table dimension bounded by a numeric input value, not from the dynamic programming recurrence itself.

Transcript excerpt

0:01 In the next section we'll look at the knapsack problem again and see a concrete example for what these pseudo polynomial algorithms can look like. Of course any actual polynomial time algorithm is also pseudo polynomial if you want, but um an example where pseudo polynomial does something interesting. I skipped the definition earlier because uh um it's coming here in more detail anyways. The knapsack problem is the following. You're you're given n objects and these each have um a weight and a value. You also have some some uh threshold or some some capacity. It's not just a It's not a threshold in the optimization sense. This is the optimization problem. Um this B is a capacity for some

0:49 container and you want to take as many objects as you can fit in your container. But what you really care about is the total value. So it's it's weighted in all all sense. So um the optimization problem asks for picking a subset of these items so that the uh weights sum up to at most B but you maximize this total value that you get from these items. And you can say this is the burglar problem. You have items of different value and weights and you want to still run fast enough or maybe you can make a more positive less criminal analogy. That's the knapsack problem. Now it is NP-hard. We've not shown that. Um

1:39 I wonder if this is This was somewhere in the exercises. You might have kicked it out. Maybe you've also seen a solution. If you think about it, this this is a problem where it's not so obvious why it would maybe have a reduction from 3-SAT or something of this sort. Because it only talks about these numbers. Also from what I'm telling you now,

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Sebastian Wild (Lectures).