Knapsack DP is a dynamic programming method used to solve the classic knapsack problem: given a set of items with specific weights and values, find the most valuable subset that fits inside a container with a maximum weight capacity.
Introduction
Knapsack problems appear whenever we must choose some objects while respecting a limited resource. Each object may consume weight, time, money, memory, or another kind of capacity, and choosing it gives us some benefit.
The difficulty is that an item can be useful on its own but prevent us from taking a better combination later. A greedy rule such as taking the most valuable item or the item with the best value-to-weight ratio does not generally work. We need to compare combinations without enumerating every subset.
Problem or motivation
There are n items. Item i has weight wi and value v. A knapsack can carry total weight at most .
i
W
We may either take or skip each item, and every item may be taken at most once. Our goal is to maximize the total value of the selected items while keeping their total weight at most W. This version is called 0/1 Knapsack because the number of copies chosen from each item is either 0 or 1.
For example, suppose W=7 and the items are:
Item
Weight
Value
1
3
4
2
2
3
3
4
5
4
5
8
Taking items 2 and 4 uses weight 2+5=7 and gives value 3+8=11. No valid selection has a larger value, so the answer is 11.
We will assume that 1≤n≤100, 1≤W≤105, and all weights and values are nonnegative. These constraints are too large for subset enumeration but suitable for a solution in O(nW) time.
Naive approach
For every item, we have two choices: take it or skip it. Therefore, there are 2n possible subsets. We could inspect every subset, calculate its total weight and value, and keep the best valid one.
This approach is correct, but its running time is exponential. Even n=50 already gives more than 1015 subsets.
The enumeration also repeats the same work. Many different sequences of earlier decisions reach the same point: we have considered the first i items and have a certain capacity available. From that point onward, the best possible continuation is the same, no matter how we reached it. Dynamic programming stores the best result for each such situation once.
Core concept
State
Define dp[i][c] as the maximum total value we can obtain using only the first i items, with total weight at most c.
The phrase at most c is important. We do not have to fill the capacity exactly. If the best selection for capacity c uses less weight, it is still valid.
Transition
Consider item i, whose weight is wi and value is vi. Any optimal selection using the first i items is in exactly one of two cases:
We skip item i. Then the answer is dp[i−1][c].
We take item i. This is possible only when wi≤c. The remaining selected items must come from the first i−1 items and may use weight at most c−wi, so this choice gives dp[i−1][c−wi]+vi.
Therefore, when wi≤c, the transition is
dp[i][c]=max(dp[i−1][c],dp[i−1][c−wi]+vi)
When wi>c, we cannot take the item, so
dp[i][c]=dp[i−1][c]
The transition is trustworthy because every valid solution either contains item i or does not contain it. We examine both possibilities, and each one reduces to an already solved state involving fewer items.
Base case, order, and answer
With no items, the best value is 0 for every capacity, so
dp[0][c]=0
We calculate rows in increasing order of i. Every state in row i uses only row i−1, which is already complete. Capacities within a row may be processed in any order in the two-dimensional version.
The final answer is
dp[n][W]
Main algorithm
The two-dimensional table is the clearest way to derive the solution, but it stores O(nW) values. Notice that row i depends only on row i−1. Once the new row has been calculated, older rows are no longer needed.
We can keep a single array. Before processing item i, let dp[c] represent the answer using the first i−1 items. While processing the item, update it with dp[c−wi]+vi.
The capacities must be processed from W down to wi. Then dp[c−wi] has not yet been changed for the current item, so it still represents a solution using only the previous items. This guarantees that item i is used at most once.
After all capacities have been processed, the invariant becomes: dp[c] is the maximum value obtainable with capacity at most c using the items handled so far.
Algorithm:
This reduces the memory from O(nW) to O(W). The time remains O(nW), which is a major improvement over the O(2n) subset enumeration.
Why the decreasing order matters
Suppose there is one item with weight 2 and value 3, and W=4.
If capacities are processed in increasing order, we first set dp[2]=3. When we later process capacity 4, the transition reads the already updated value dp[2]=3 and sets dp[4]=6. This has used the same item twice, which is forbidden in 0/1 Knapsack.
With decreasing order, capacity 4 is processed before capacity 2. At that moment, dp[2] still belongs to the previous set of items, so the current item cannot use itself.
This gives a useful rule:
Each item may be used once: process capacities in decreasing order.
Each item may be used any number of times: process capacities in increasing order.
Important state variations
The transition pattern stays similar across many Knapsack problems, but the exact meaning of the state changes its initialization, loop order, and final answer. Always define the state in one precise sentence before writing code.
Exact total weight
In the standard problem, dp[c] means weight at mostc. Initializing every state to 0 is correct because the empty selection is valid for every capacity.
Suppose instead that dp[c] means the maximum value among selections whose total weight is exactlyc. Now the empty selection reaches only weight 0. We must initialize dp[0]=0 and dp[c]=−∞ for every c>0.
When taking an item, transition only from a reachable state. For an exact-weight-W problem, the answer is dp[W]; if it remains unreachable, no valid selection exists.
Subset sum
Subset sum asks whether some subset has total weight exactly S. Values are unnecessary. Define can[c] to mean that sum c is reachable.
Initialize can[0]=true and every other state to false. For each number ai, process c from S down to ai and set
can[c]=can[c]∨can[c−ai]
The decreasing order again ensures that each number is used at most once.
Unbounded knapsack
In unbounded knapsack, every item may be selected any number of times. The one-dimensional transition is still
dp[c]=max(dp[c],dp[c−wi]+vi)
but now capacities are processed from wi up to W.
Increasing order allows dp[c−wi] to already contain the current item. That is exactly what we want when another copy is allowed.
Bounded knapsack
If item i may be used at most ki times, repeating the 0/1 update ki times is correct but may be too slow. A common optimization splits the copies into groups of sizes 1,2,4,… plus the remaining amount. Each group becomes one 0/1 item whose weight and value are multiplied by the group size.
This represents every number of copies from 0 to ki while creating only O(log(ki+1)) groups.
DP by value
The standard solution uses weight as a DP dimension, so it is useful only when W is reasonably small. If W is huge but the sum of all values is small, reverse the state.
Let V=∑i=1nvi, and define min_weight[x] as the minimum total weight needed to obtain value exactly x using the processed items.
Initialize min_weight[0]=0 and all other states to +∞. For each item, process values in decreasing order and use the transition
The answer is the largest value x for which min_weight[x]≤W. This solution takes O(nV) time and O(V) memory.
The broader lesson is that Knapsack does not always need to be indexed by weight. Choose the dimension whose total range is small enough.
Restoring the selected items
If the problem asks which items were chosen, the two-dimensional table gives a simple path-restoration method. Start from (i,c)=(n,W).
If dp[i][c]=dp[i−1][c], we may skip item i. Otherwise, item i must be part of the restored solution; record it and replace c with c−wi. Then decrease i and continue.
When both taking and skipping give the same optimal value, either choice may lead to a valid optimal solution. The one-dimensional optimization does not keep every previous row, so use the full table or store additional decisions when restoration is required.
Implementation
Complexity
Time:O(nW)
Memory:O(W)
1. Create dp[0..W] and initialize every value to 0.
2. For every item i from 1 to n:
2.1. For capacity c from W down to w[i]:
- skip = dp[c];
- take = dp[c - w[i]] + v[i];
- dp[c] = max(skip, take).
3. Return dp[W].
#include <bits/stdc++.h>using namespace std;const int N = 100200;int w[N];long long v[N];long long dp[N];int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin >> n >> W; for(int i = 1; i <= n; i++){ cin >> w[i]>> v[i];} for(int i = 1; i <= n; i++){ for(int c = W; c >= w[i]; c--){ dp[c] = max(dp[c], dp[c - w[i]] + v[i]);}} cout << dp[W]<< endl; return 0;}