01 Knapsack

Given N item types and a knapsack with capacity V. Each item can be selected at most once, with volume v[i] and value w[i]. Find the maximum total value without exceeding capacity. Constraints: 0 < N, V <= 1000; 0 < v[i], w[i] <= 1000.

The classic 01 knapsack uses a two-state transition approach: either skip the current item or include it. Time complexity is O(NV), with rolling array optimization to reduce space usage.

#include <bits/stdc++.h>
int main() {
    int n, cap;
    std::cin >> n >> cap;
    std::vector<int> vol(n), val(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> vol[i] >> val[i];
    }
    std::vector<int> prev(cap + 1), curr(cap + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= cap; ++j) {
            curr[j] = prev[j];
            if (j >= vol[i]) {
                curr[j] = std::max(curr[j], prev[j - vol[i]] + val[i]);
            }
        }
        prev.swap(curr);
    }
    std::cout << prev[cap] << "\n";
    return 0;
}

Complete Knapsack

Given N item types with unlimited suply, each with volume v[i] and value w[i]. Find the maximum value with capacity V. Constraints: 0 < N, V <= 1000.

The key difference from 01 knapsack is allowing multiple selections of the same item. The transition uses the current row value instead of previous row.

#include <bits/stdc++.h>
int main() {
    int n, cap;
    std::cin >> n >> cap;
    std::vector<int> vol(n), val(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> vol[i] >> val[i];
    }
    std::vector<int> prev(cap + 1), curr(cap + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= cap; ++j) {
            curr[j] = prev[j];
            if (j >= vol[i]) {
                curr[j] = std::max(curr[j], curr[j - vol[i]] + val[i]);
            }
        }
        prev.swap(curr);
    }
    std::cout << prev[cap] << "\n";
    return 0;
}

Bounded Knapsack (Naive)

Given N item types with limited counts s[i], each with volume v[i] and value w[i]. Find maximum value within capacity V. Constraints: 0 < N, V <= 100.

For each item type, enumerate all possible selection counts from 0 to s[i].

#include <bits/stdc++.h>
int main() {
    int n, cap;
    std::cin >> n >> cap;
    std::vector<int> vol(n), val(n), cnt(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> vol[i] >> val[i] >> cnt[i];
    }
    std::vector<int> prev(cap + 1), curr(cap + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= cap; ++j) {
            curr[j] = prev[j];
            for (int k = 1; k <= cnt[i] && j >= k * vol[i]; ++k) {
                curr[j] = std::max(curr[j], prev[j - k * vol[i]] + k * val[i]);
            }
        }
        prev.swap(curr);
    }
    std::cout << prev[cap] << "\n";
    return 0;
}

Bounded Knapsack with Binary Decomposition

Same problem with larger constraints. N <= 1000, V <= 2000.

Binary decomposition converts bounded items into multiple 01 knapsack items. Each count s is broken into powers of 2 (1, 2, 4, 8...), achieving O(NV log S) complexity.

#include <bits/stdc++.h>
int main() {
    int n, cap;
    std::cin >> n >> cap;
    std::vector<int> vol(n), val(n), cnt(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> vol[i] >> val[i] >> cnt[i];
    }
    std::vector<int> decomposedVol, decomposedVal;
    for (int i = 0; i < n; ++i) {
        for (int k = 1; cnt[i] > 0; k <<= 1) {
            int take = std::min(k, cnt[i]);
            decomposedVol.push_back(vol[i] * take);
            decomposedVal.push_back(val[i] * take);
            cnt[i] -= take;
        }
    }
    int items = decomposedVol.size();
    std::vector<int> prev(cap + 1), curr(cap + 1, 0);
    for (int i = 0; i < items; ++i) {
        for (int j = 0; j <= cap; ++j) {
            curr[j] = prev[j];
            if (j >= decomposedVol[i]) {
                curr[j] = std::max(curr[j], prev[j - decomposedVol[i]] + decomposedVal[i]);
            }
        }
        prev.swap(curr);
    }
    std::cout << prev[cap] << "\n";
    return 0;
}

Bounded Knapsack with Monotonic Queue

Larger constraints: V <= 20000.

State transitions for positions with the same modulo value form a sliding window pattern. The equation dp[j] = max(dp[j], dp[j-kv] + kw) transforms in to dp[j] - j/vw = max(dp[j-kv] - k*w), which allows O(NV) optimization using a monotonic queue.

#include <bits/stdc++.h>
struct Item {
    int idx, value;
};
int vol[1005], val[1005], cnt[1005], dp[20005];
Item q[20005];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, cap;
    std::cin >> n >> cap;
    for (int i = 0; i < n; ++i) {
        std::cin >> vol[i] >> val[i] >> cnt[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int r = 0; r < vol[i]; ++r) {
            int left = 0, right = 0;
            for (int pos = r, step = 0; pos <= cap; pos += vol[i], ++step) {
                while (left < right && q[left].idx < step - cnt[i]) ++left;
                int base = dp[pos] - step * val[i];
                while (left < right && q[right - 1].value < base) --right;
                q[right++] = {step, base};
                dp[pos] = q[left].value + step * val[i];
            }
        }
    }
    std::cout << dp[cap] << "\n";
    return 0;
}

Mixed Knapsack

N items with s[i] indicating availability: -1 means single item, 0 means unlimited, psoitive means limited count. Goal is maximum value with capacity V. N, V <= 1000.

Convert all items to 01 knapsack format: unlimited items become V/v[i] copies, then apply binary decomposition.

#include <bits/stdc++.h>
int main() {
    int n, cap;
    std::cin >> n >> cap;
    std::vector<int> itemsVol, itemsVal;
    for (int i = 0; i < n; ++i) {
        int v, w, s;
        std::cin >> v >> w >> s;
        if (s == -1) s = 1;
        else if (s == 0) s = cap / v;
        for (int k = 1; s > 0; k <<= 1) {
            int batch = std::min(k, s);
            itemsVol.push_back(v * batch);
            itemsVal.push_back(w * batch);
            s -= batch;
        }
    }
    int m = itemsVol.size();
    std::vector<int> prev(cap + 1), curr(cap + 1, 0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= cap; ++j) {
            curr[j] = prev[j];
            if (j >= itemsVol[i]) {
                curr[j] = std::max(curr[j], prev[j - itemsVol[i]] + itemsVal[i]);
            }
        }
        prev.swap(curr);
    }
    std::cout << prev[cap] << "\n";
    return 0;
}

Two-Dimensional Cost Knapsack

N items with both volume v[i] and weight m[i], each selectable once. Find maximum value with capacity V and weight limit M. N <= 1000, V, M <= 100.

Similar to 01 knapsack but tracking two dimensions simultaneously. Complexity is O(N * V * M).

#include <bits/stdc++.h>
int main() {
    int n, volCap, weightCap;
    std::cin >> n >> volCap >> weightCap;
    std::vector<int> vol(n), weight(n), val(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> vol[i] >> weight[i] >> val[i];
    }
    std::vector<std::vector<int>> prev(volCap + 1, std::vector<int>(weightCap + 1));
    std::vector<std::vector<int>> curr(volCap + 1, std::vector<int>(weightCap + 1));
    for (int i = 0; i < n; ++i) {
        for (int v = 0; v <= volCap; ++v) {
            for (int w = 0; w <= weightCap; ++w) {
                curr[v][w] = prev[v][w];
                if (v >= vol[i] && w >= weight[i]) {
                    curr[v][w] = std::max(curr[v][w], prev[v - vol[i]][w - weight[i]] + val[i]);
                }
            }
        }
        prev.swap(curr);
    }
    std::cout << prev[volCap][weightCap] << "\n";
    return 0;
}

Group Knapsack

N groups, each containing multiple items. At most one item can be selected from each group. Find maximum value within capacity V. N, V <= 100.

For each group, either select no items or choose exactly one item from the group.

#include <bits/stdc++.h>
struct Item {
    int volume, value;
};
int main() {
    int n, cap;
    std::cin >> n >> cap;
    std::vector<std::vector<Item>> groups(n);
    for (int i = 0; i < n; ++i) {
        int m;
        std::cin >> m;
        groups[i].resize(m);
        for (int j = 0; j < m; ++j) {
            std::cin >> groups[i][j].volume >> groups[i][j].value;
        }
    }
    std::vector<int> prev(cap + 1), curr(cap + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int v = 0; v <= cap; ++v) {
            curr[v] = prev[v];
            for (const auto& itm : groups[i]) {
                if (v >= itm.volume) {
                    curr[v] = std::max(curr[v], prev[v - itm.volume] + itm.value);
                }
            }
        }
        prev.swap(curr);
    }
    std::cout << prev[cap] << "\n";
    return 0;
}