0/1 Knapsack

Key Signals & Indicators

• Need to select elements under weight or capacity constraints
• Each element can be chosen at most once (0 or 1 choice)
• Problem exhibits overlapping subproblems (e.g. subset sum)

// C++ 0/1 Knapsack Template (Space Optimized)
#include <vector>
#include <algorithm>

int knapsack01(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
    // dp[w] stores max value for capacity w
    std::vector<int> dp(capacity + 1, 0);
    
    for (size_t i = 0; i < weights.size(); ++i) {
        // Iterate backward to prevent using same element multiple times
        for (int w = capacity; w >= weights[i]; --w) {
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}