The Knapsack Family: 0/1, Unbounded, Subset Sum Bitset & Bounded Knapsack (Binary Splitting / Monotonic Queue)

1. The Four Canonical Knapsack Variants

Given $N$ item types with weights $w_i$, values $v_i$, and knapsack capacity $W$:

1. 0/1 Knapsack ($c_i \in \{0, 1\}$): Each item taken at most once. 1D recurrence iterates $w$ backward from $W$ down to $w_i$: $$dp[w] = \max(dp[w],\; dp[w - w_i] + v_i)$$
2. Unbounded / Complete Knapsack ($c_i \in \{0, 1, 2, \dots\}$): Unlimited copies of each item. 1D recurrence iterates $w$ forward from $w_i$ up to $W$ so $dp[w - w_i]$ already includes item $i$: $$dp[w] = \max(dp[w],\; dp[w - w_i] + v_i)$$
3. Subset Sum Bitset Acceleration ($v_i = 0/1$ feasibility): Can a subset sum to $w$? Pack the boolean array into 64-bit machine words (std::bitset). Adding item $w_i$ becomes a single word-parallel shift-OR: $$\text{bits} \mathrel{|=} (\text{bits} \ll w_i) \quad \implies \quad O\!\left(\frac{N \cdot W}{64}\right)$$
4. Bounded Knapsack ($c_i \in \{0, 1, \dots, k_i\}$): At most $k_i$ copies of item $i$. Naive transition checks all $c \in [0..k_i]$ in $O(N W \cdot k_i)$. How do we remove the $k_i$ factor?

2. The $\sqrt{S}$ Frequency Compression Trick for Subset Sum ($\sum w_i = S$)

When the sum of all item weights is $\sum_{i=1}^N w_i = S$, at most $O(\sqrt{S})$ distinct weight values can exist! Why? Because the minimum sum of $d$ distinct positive integers is $1 + 2 + \dots + d = d(d+1)/2 \le S \implies d \le \sqrt{2S}$. By grouping identical weights into (weight, count) pairs and applying binary splitting (or packing pairs of equal weights into a next-level weight $2w$ until at most 2 copies of each weight remain), Subset Sum on $\sum w_i = S$ runs in $O\!\left(\frac{S \sqrt{S}}{64}\right)$ time!

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <deque>
#include <vector>

struct BoundedItem {
    int weight;
    long long value;
    int count;
};

// 1. Bounded Knapsack in O(W * sum(log k_i)) via Binary Splitting
long long bounded_knapsack_binary_split(const std::vector<BoundedItem>& items, int capacity) {
    std::vector<long long> dp(capacity + 1, 0);

    auto apply_01_item = [&](int w, long long v) {
        for (int cap = capacity; cap >= w; --cap) {
            dp[cap] = std::max(dp[cap], dp[cap - w] + v);
        }
    };

    for (const auto& item : items) {
        int rem = item.count;
        for (int b = 1; b <= rem; b <<= 1) {
            int bundle_w = b * item.weight;
            if (bundle_w <= capacity) {
                apply_01_item(bundle_w, b * item.value);
            }
            rem -= b;
        }
        if (rem > 0 && rem * item.weight <= capacity) {
            apply_01_item(rem * item.weight, rem * item.value);
        }
    }
    return dp[capacity];
}

// 2. Bounded Knapsack in Strict O(N * W) Time via Monotonic Deque over Residue Classes
long long bounded_knapsack_monotonic_queue(const std::vector<BoundedItem>& items, int capacity) {
    std::vector<long long> dp(capacity + 1, 0);
    std::deque<std::pair<int, long long>> dq; // (quotient q, shifted_val = dp[q*w + r] - q*v)

    for (const auto& item : items) {
        const int w = item.weight;
        const long long v = item.value;
        const int k = item.count;
        if (w > capacity || k == 0) continue;

        for (int r = 0; r < w; ++r) {
            dq.clear();
            int max_q = (capacity - r) / w;
            for (int q = 0; q <= max_q; ++q) {
                long long shifted = dp[q * w + r] - q * v;
                while (!dq.empty() && dq.back().second <= shifted) {
                    dq.pop_back();
                }
                dq.emplace_back(q, shifted);
                // Evict window elements older than q - k
                if (dq.front().first < q - k) {
                    dq.pop_front();
                }
                dp[q * w + r] = dq.front().second + q * v;
            }
        }
    }
    return dp[capacity];
}

// 3. O(N * W / 64) Word-Parallel Subset Sum using std::bitset
template <std::size_t MAXW = 100001>
bool subset_sum_bitset(const std::vector<int>& weights, int target) {
    if (target < 0 || static_cast<std::size_t>(target) >= MAXW) return false;
    std::bitset<MAXW> reachable;
    reachable.set(0);
    for (int w : weights) {
        reachable |= (reachable << w);
    }
    return reachable.test(target);
}