The 0/1 knapsack problem involves selecting items where each item can be either taken or left (0 or 1 decision). Given N items with weights and values, maximize the total value without exceeding cpaacity V.

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 1001;
int dp[MAX][MAX];
int weights[MAX], values[MAX];

int main() {
    int N, capacity;
    cin >> N >> capacity;
    
    for(int i = 1; i <= N; i++) {
        cin >> weights[i] >> values[i];
    }
    
    for(int item = 1; item <= N; item++) {
        for(int cap = 0; cap <= capacity; cap++) {
            dp[item][cap] = dp[item-1][cap];
            if(cap >= weights[item]) {
                dp[item][cap] = max(dp[item][cap], 
                                   dp[item-1][cap-weights[item]] + values[item]);
            }
        }
    }
    
    cout << dp[N][capacity];
    return 0;
}

Space Optimization

The solution can be optimized to use O(V) space by using a 1D array and iterating backwards:

int optimized[MAX];
for(int item = 1; item <= N; item++) {
    for(int cap = capacity; cap >= weights[item]; cap--) {
        optimized[cap] = max(optimized[cap], 
                            optimized[cap-weights[item]] + values[item]);
    }
}

Unbounded Knapsack Problem

Items can be selected multiple times. The key difference is iterating forwards in the capacity loop:

for(int item = 1; item <= N; item++) {
    for(int cap = weights[item]; cap <= capacity; cap++) {
        dp[cap] = max(dp[cap], dp[cap-weights[item]] + values[item]);
    }
}

Bounded Knapsack Problem

Items have limited quatnities. The solution involves an additional loop for item counts:

for(int item = 1; item <= N; item++) {
    for(int cap = capacity; cap >= weights[item]; cap--) {
        for(int count = 1; count <= quantities[item] && count*weights[item] <= cap; count++) {
            dp[cap] = max(dp[cap], dp[cap-count*weights[item]] + count*values[item]);
        }
    }
}

Binary Optimization

Improves efficiency by representing item counts as powers of 2:

for(int item = 1; item <= N; item++) {
    int remaining = quantities[item];
    for(int k = 1; remaining > 0; k <<= 1) {
        int take = min(k, remaining);
        for(int cap = capacity; cap >= take*weights[item]; cap--) {
            dp[cap] = max(dp[cap], dp[cap-take*weights[item]] + take*values[item]);
        }
        remaining -= take;
    }
}