Advanced Algorithms (Winter 2026-27) - 03-03 Knapsack DP solution

Overview

Sebastian Wild explains the standard knapsack dynamic program and why its O(nB) table-filling time is pseudo-polynomial when capacity B can be exponentially large relative to its binary encoding. He then transposes the table to track minimum weight for each exact value, yielding a second pseudo-polynomial approach when total item value is small and foreshadowing how value rounding can support approximation algorithms.

Key takeaways

Binary encoding makes a numerical value B take only O(log B) bits, so the capacity-indexed knapsack algorithm's O(nB) time is pseudo-polynomial rather than polynomial in input length.
The capacity DP stores maximum attainable value for each item prefix and capacity, and backtracing the include or exclude transitions recovers an optimal subset.
A complementary DP stores the minimum weight required to attain each exact value; unreachable values receive infinity, and the final solution is the greatest value whose minimum weight fits the capacity.
When the sum V of item values is small, the exact-value DP uses about O(nV) table entries even if capacities and weights are large.
Value rounding can collapse nearby value columns to shrink the exact-value table and support approximation, while keeping the knapsack capacity constraint strict.

Chapters

0:00 Knapsack and the Meaning of Pseudo-Polynomial Time

A knapsack instance has n items with weights and values, plus a capacity constraint; the goal is to maximize the value of the selected subset.
Binary encoding represents an integer of magnitude x using about log x bits, so an algorithm taking time proportional to x may be exponential in input length.
A running time polynomial in the input encoding size and a numerical input parameter such as capacity is called pseudo-polynomial.

3:30 Capacity-Indexed DP, Item Choices, and Backtracing

The first dynamic program indexes subproblems by an item prefix i and a capacity limit b, choosing whether to include item i.
For each table entry, compare the best value without item i against its value plus the best result at capacity b minus its weight.
In the illustrated capacity-7 example, the optimum value is 90, recovered by backtracing the choices that select items B and D.
The bottom-right table entry gives the optimal value; tracing whether each entry came from above or from the include-item transition reconstructs the chosen subset.

11:15 Why the Capacity DP Is Pseudo-Polynomial

The capacity table has roughly (n+1)(B+1) entries, with a constant number of arithmetic operations and comparisons per entry.
Because B may be exponentially large in its binary encoding, the O(nB) algorithm can be exponential in ordinary input length.
Accounting for bit-level arithmetic adds logarithmic costs, while the overall running time remains polynomial in input size and the largest encoded integer.

14:30 Transpose the Table to Track Exact Values

When weights and capacities are large but item values are small, the capacity-indexed table is too wide to be useful.
Let V be the sum of all item values; if each value is at most n squared, then V is at most n cubed.
Define each entry as the minimum weight needed to achieve exactly value v using the first i items, and use infinity when that exact value is unreachable.
The include-item transition adds the item's weight to the entry for the remaining value; the exclude-item transition carries forward the previous prefix's weight.

22:25 Exact-Value DP Examples and Feasibility

For two items, the example cannot achieve exact value 6: neither excluding the second item nor including it leaves a reachable required value, so the entry is infinity.
For exact value 5 using the first three items, the minimum-weight solution has weight 9 by selecting items A and B.
After filling the value-indexed table, scan the row for all values whose minimum weight is at most the knapsack capacity, then choose the largest such value.

26:20 Value-Based Complexity, Approximation, and Broader Context

The value-indexed table has about nV entries, making it pseudo-polynomial in the sum of item values rather than in capacity.
Capacity-indexed and value-indexed dynamic programs suit different parameter ranges; neither is uniformly better when weights, capacity, and values vary.
Rounding or grouping value columns can reduce the table width and lead toward approximation algorithms; relaxing value precision is possible without violating the hard capacity constraint.
Dynamic programming produces pseudo-polynomial algorithms for some problems, while finding evidence that problems such as traveling salesperson lack such algorithms requires further complexity theory.

Transcript excerpt

0:01 Okay, let's do um, a very short recap. We've been looking at the knapsack problem in the context of this uh, chapter on pseudo-polynomial algorithms, which were algorithms where the running time in a strict sense is exponential, but it is polynomial in a specific parameter of the input, something that we will talk about in more detail in next in the next unit. Uh, namely the largest integer, the largest number that occurs in the input. And where did that discrepancy come from? Well, if you have an input that consists of numbers, you shall use a sensible encoding. And uh, a sensible encoding is a binary code for the numbers, say, uh, giving giving them in in uh, base

0:49 two. And then, a number of size n only takes roughly log n bits, big O of log n bits. By the way, even if you don't know how big the number is, right? There's Elias gamma codes and things like that. So, even if you wanted to specify a number where you don't have to specify up front how many bits it takes, you could still do it in big O of log n bits. You lose a factor two, but not more. Uh, so, we can encode numbers if all we need is this numerical value very concisely, very succinctly. Uh, on the flip side, this means if a problem consists of numbers that can be small written in small things, then taking time proportional to the value of the number is in principle exponential. But we call it pseudo-polynomial

1:36 because it sometimes is closer to tractable. And one example was this knapsack problem. Uh, the formal definition here uh, again was was this one. We have items and different ones. Uh-huh. I don't love the new setup

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