Knapsack DP: capacity tables and grid paths · 2 of 2
Knapsack
Choose items under a weight limit with a state for the items considered and the capacity, keep one row of the table, and reuse it for reachable sums, counts and unlimited copies.
Books1
Links6
- Algorithms, Chapter 3: Dynamic programming Section 3.8 builds the Subset Sum table from a recursion that takes or skips each number, and shows that the table is slower than trying every subset when the target is far larger than 2^n. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)
- Knapsack DP The three knapsack questions of this lesson, the best value, the reachable weights and the number of ways to fill the bag, with Dice Combinations worked through and a graded problem list. usaco.guide (opens in a new tab)
- Knapsack 1 0/1 knapsack as stated in this lesson, with 100 items and a capacity of up to 10^5. Values go up to 10^9, so the totals need 64-bit integers. atcoder.jp (opens in a new tab)
- Knapsack 2 The same problem with a capacity of up to 10^9 and values of at most 1,000, where a table over capacities is impossible and the states have to be total values. atcoder.jp (opens in a new tab)
- Knapsack Problem 0/1, complete and multiple-copy knapsack, with the one-row loop running in decreasing order for 0/1 items and increasing order for unlimited ones. cp-algorithms.com (opens in a new tab)
- 背包 DP 基础 (Knapsack DP basics) The 0/1, unbounded and multiple-copy knapsacks, why the one-row loop runs downward for one copy and upward for unlimited copies, and counting the ways to fill a bag. oi-wiki.org (opens in a new tab)