--- title: "Dynamic Programming with a Capacity: Knapsack" description: "A 0/1 knapsack table stores the best value for an item prefix and an allowed capacity. With integer weights, its O(n(W+1)) work depends on numeric capacity W, which may be large compared with the numb" 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-11-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 A 0/1 knapsack table stores the best value for an item prefix and an allowed capacity. With integer weights, its O(n(W+1)) work depends on numeric capacity W, which may be large compared with the number of bits used to write it. This is pseudo-polynomial time. 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 - Explain why increasing numeric capacity W adds table columns with item count fixed, and why W can be large compared with its binary encoding length ## Lesson: Packing the best bag by table As with two-string tables, define both indices. In 0/1 knapsack, each item can be taken at most once. Use positive integer weights and nonnegative values. K(i,c) is the best total value using the first i items with total weight at most c. Rows count available items; columns give allowed capacity from 0 to W. Initialize K(0,c)=0 and K(i,0)=0. For item i with weight w_i and value v_i, skipping gives K(i-1,c). If w_i is at most c, taking gives v_i+K(i-1,c-w_i). Store the larger value. If the item does not fit, use only the skip value. Both choices use the previous row, which prevents taking item i twice. Fit alone does not mean taking the item is best. **Example.** For a small instance, you can list feasible subsets and compare totals. Items 1, 2 and 3 have weights 2, 3 and 4, and values 4, 5 and 6. Capacity is 5. Items 1 and 2 give weight 5 and value 9; other pairs do not fit. The table agrees: row 2 at capacity 5 compares skip value 4 with take value 5+K(1,2)=9. Row 3 compares 9 with 6+K(2,1)=6, keeping 9. *(drawing: Each cell lists one row. Values within a row follow capacities 0 through 5.)* The final value is K(n,W). To recover items, compare K(i,c) with K(i-1,c). If equal, you may skip item i and move up. Otherwise take item i, subtract w_i from c, and move up. Repeat until no items remain. A tie may allow more than one optimal set. The final value alone does not identify its items. The (n+1)(W+1) cells take constant work each in the usual arithmetic model. O(n(W+1)) bounds work by a constant times n(W+1) for large inputs. Input size counts all encoded bits. For W>0, log2(W) is the exponent in 2^log2(W)=W. Rounded down, plus 1, it counts W's binary bits. Thus W can grow exponentially in its bit length. Work is polynomial in n and W, not binary input size: pseudo-polynomial. Doubling weights alone leaves the columns unchanged if capacity W stays fixed. Doubling both weights and capacity changes W+1 columns to 2W+1, roughly twice as many for large W. The number of item rows stays the same. This scaling preserves which subsets fit, but increases the work of the uncompressed capacity table. **Recap.** Compare skip with take-once in each capacity state. Trace back for the items. Table work follows numeric capacity, not just its encoded length. *Original lesson, questions, worked solutions and flashcards written for this dataset.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Dynamic Programming on Two Sequences](https://lightmysky.com/learn/computing/dynamic-programming-on-two-sequences-mt_uNUgHcKKQN) ## Optional connections - [Hexadecimal as Binary Shorthand](https://lightmysky.com/learn/computing/hexadecimal-as-binary-shorthand-mt_OV6PHdnU6N) ## 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)