Knapsack DP

Concept

The 0/1 Knapsack problem asks: given items with weights and values, and a capacity W, maximize total value without exceeding W. Each item can be taken or skipped. Bottom-up tabulation builds a 2D table dp[i][w] where i is the number of items considered and w is the current capacity.

When to Use

• ▸Selecting items with weight/size constraints to maximize value
• ▸Budget allocation problems
• ▸Subset selection with a capacity limit
• ▸Any problem where you pick/skip items with a total constraint

Intuition

Build a table row by row. Row i represents 'best value using only the first i items'. For each item i and capacity w, you have two choices: skip item i (take dp[i-1][w]) or take it if it fits (take val[i-1] + dp[i-1][w-wt[i-1]]). Pick the max. The table fills from small subproblems (fewer items, less capacity) to the full problem. The answer is at dp[n][W] — all items considered, full capacity available.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, W;
    cin >> n >> W;

    vector<int> val(n), wt(n);
    for(int i = 0; i < n; i++) cin >> wt[i] >> val[i];

    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    for(int i = 1; i <= n; i++){
        for(int w = 0; w <= W; w++){
            dp[i][w] = dp[i-1][w];
            if(wt[i-1] <= w){
                dp[i][w] = max(dp[i][w], val[i-1] + dp[i-1][w-wt[i-1]]);
            }
        }
    }

    cout << dp[n][W] << "\n";

    return 0;
}

// Sample Input:
// 4 7
// 1 1
// 3 4
// 4 5
// 5 7
//
// Sample Output:
// 9