---
title: "Dynamic Programming with a Capacity: Knapsack"
description: "The knapsack table is indexed by item and by remaining capacity, which makes its size depend on the numbers in the input rather than on how many there are. That is why the method is called pseudo-poly"
canonical: https://lightmysky.com/learn/computing/dynamic-programming-with-a-capacity-knapsack-mt_T5pbU_DpdC
source: https://lightmysky.com/learn/computing/dynamic-programming-with-a-capacity-knapsack-mt_T5pbU_DpdC.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Dynamic Programming with a Capacity: Knapsack

The knapsack table is indexed by item and by remaining capacity, which makes its size depend on the numbers in the input rather than on how many there are. That is why the method is called pseudo-polynomial and why doubling the weights doubles the work.

Subject: Computing · Area: Algorithms & Data Structures · Ages 20 to 22
Page: https://lightmysky.com/learn/computing/dynamic-programming-with-a-capacity-knapsack-mt_T5pbU_DpdC

## Ready when they can

- Fill a knapsack table for five items and read off which items were taken
- Explain why the table has capacity as one of its axes
- Say why an input written with larger numbers costs more without holding more items

## Lesson: Packing the best bag by table

The knapsack table is indexed by item and by remaining capacity. Each row adds one item to the choice, each column a capacity. The cell asks: take this item or skip it.

**Example.** Three items weigh 2, 3, and 4 with values 3, 4, and 5. Capacity is 5. The table fills, the corner reads 7, and the traceback takes the first two items. Weight 5, value 7.

Capacity is an axis because the choice depends on room left. The same item is worth taking with space to spare and wrong when the bag is nearly full. The column carries that context.

**Tip.** The table size follows the numbers, not just the item count. Doubling all weights doubles the columns and the work. That number-driven cost is why the method is called pseudo-polynomial.

**Recap.** Index by item and capacity, read the corner, and note the cost follows the numbers.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Hexadecimal as Binary Shorthand](https://lightmysky.com/learn/computing/hexadecimal-as-binary-shorthand-mt_OV6PHdnU6N)
- [Dynamic Programming on Two Sequences](https://lightmysky.com/learn/computing/dynamic-programming-on-two-sequences-mt_uNUgHcKKQN)

## Opens up

- [Shortest Paths with Negative Weights and Between All Pairs](https://lightmysky.com/learn/computing/shortest-paths-with-negative-weights-and-between-all-pairs-mt_e8szFezaxO)