The 0/1 Knapsack problem: given n items each with weight w[i] and value v[i], and a knapsack of capacity W, find the maximum value subset with total weight at most W. Each item is either taken (1) or not taken (0). DP solves it in O(nW) time with a 2D table.
int knapsack(vector<int>& w, vector<int>& v, int W) {
int n=w.size();
vector<vector<int>> dp(n+1, vector<int>(W+1,0));
for(int i=1;i<=n;i++)
for(int j=0;j<=W;j++) {
dp[i][j]=dp[i-1][j];
if(w[i-1]<=j) dp[i][j]=max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1]);
}
return dp[n][W];
}dp[i][j] = max value using first i items with capacity j. For item i: either skip it (dp[i-1][j]) or take it if it fits (dp[i-1][j-w[i]]+v[i]). Take the maximum.
Fill the table row by row. Row i depends only on row i-1, so we can optimize space to O(W) by using a single 1D array and iterating j backwards to avoid using updated values.
To reconstruct which items were taken: traverse the table backwards from dp[n][W]. If dp[i][j] != dp[i-1][j], item i was included. Reduce j by w[i] and continue.
Unbounded knapsack allows taking each item multiple times — iterate j forwards. Fractional knapsack allows fractions — use greedy by value/weight ratio, no DP needed.
The 0/1 Knapsack problem is called "0/1" because:
The DP recurrence for 0/1 Knapsack is:
Time and space complexity of the DP Knapsack solution are: