Knapsack Helpers
(algo/dp/knapsack.hpp)

View this file on GitHub
Last update: 2026-08-12 05:02:13+09:00
Include: #include "algo/dp/knapsack.hpp"

Overview

This header provides small, explicit helpers for common subset-sum and knapsack DP patterns. The public namespace is m1une::algo.

Weights and capacities are nonnegative. Ranges are indexed by exact sum, capacity, or value depending on the function.

Functions

Function	Description	Complexity
`std::vector<char> subset_sum_reachable(const std::vector<int>& weights, int limit)`	Returns a vector where `result[s]` says whether sum `s` is reachable.	$O(NL / W + L)$ time, $O(L / W)$ working memory plus $O(L)$ returned memory
`int subset_sum_max_value(const std::vector<int>& weights, int limit)`	Returns the maximum reachable subset sum not exceeding `limit`.	$O(NL / W)$ time, $O(L / W)$ memory
`zero_one_knapsack_max_value(weights, values, capacity, neg_inf)`	Returns max value for each capacity at most `c`.	$O(NC)$ time, $O(C)$ memory
`bounded_knapsack_max_value(weights, values, counts, capacity, neg_inf)`	Returns max value for each capacity at most `c` with item limits.	$O(NC)$ time, $O(C)$ memory
`zero_one_knapsack_min_weight_for_value(weights, values, value_limit, inf)`	Returns minimum exact weight for each total value.	$O(NV)$ time, $O(V)$ memory

Here L is limit, C is capacity, V is value_limit, and W is the number of bits in an unsigned machine word.

The max-value functions return arrays of length capacity + 1; entry c is the best value using total weight at most c. The min-weight function returns exact-value costs, so unreachable values contain inf.

subset_sum_max_value treats every input weight as both its cost and its value. Each weight can be selected at most once. Unlike subset_sum_reachable, it does not materialize all limit + 1 answers, so its total memory remains packed.

Example

#include "algo/dp/knapsack.hpp"

#include <iostream>
#include <vector>

int main() {
    std::vector<int> weights = {2, 3, 4};
    std::vector<long long> values = {4, 5, 7};

    std::vector<long long> best =
        m1une::algo::zero_one_knapsack_max_value(weights, values, 5);
    std::cout << best[5] << '\n';

    std::cout << m1une::algo::subset_sum_max_value(weights, 6) << '\n';
}

Required by

Verified with

verify/algo/dp/knapsack.test.cpp

Code

#ifndef M1UNE_ALGO_DP_KNAPSACK_HPP
#define M1UNE_ALGO_DP_KNAPSACK_HPP 1

#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <deque>
#include <limits>
#include <vector>

namespace m1une {
namespace algo {

namespace internal {

using SubsetSumWord = unsigned long long;

inline std::vector<SubsetSumWord> subset_sum_reachability_bits(
    const std::vector<int>& weights,
    int limit
) {
    assert(0 <= limit);
    using Word = SubsetSumWord;
    constexpr int word_bits = std::numeric_limits<Word>::digits;

    const std::size_t bit_count = std::size_t(limit) + 1;
    std::vector<Word> bits((bit_count + word_bits - 1) / word_bits, Word(0));
    bits[0] = Word(1);

    auto trim = [&]() {
        const int extra = int(bit_count % word_bits);
        if (extra != 0) {
            bits.back() &= (Word(1) << extra) - Word(1);
        }
    };

    for (int weight : weights) {
        assert(0 <= weight);
        if (weight == 0 || limit < weight) continue;

        const std::size_t word_shift = std::size_t(weight / word_bits);
        const int bit_shift = weight % word_bits;
        for (std::size_t i = bits.size() - word_shift; i-- > 0;) {
            const Word source = bits[i];
            if (source == Word(0)) continue;
            const std::size_t target = i + word_shift;
            bits[target] |= source << bit_shift;
            if (bit_shift != 0 && target + 1 < bits.size()) {
                bits[target + 1] |= source >> (word_bits - bit_shift);
            }
        }
        trim();
    }
    return bits;
}

}  // namespace internal

inline std::vector<char> subset_sum_reachable(const std::vector<int>& weights, int limit) {
    using Word = internal::SubsetSumWord;
    constexpr int word_bits = std::numeric_limits<Word>::digits;
    const std::vector<Word> bits =
        internal::subset_sum_reachability_bits(weights, limit);

    std::vector<char> reachable(std::size_t(limit) + 1, 0);
    for (int sum = 0; sum <= limit; ++sum) {
        reachable[sum] = char((bits[std::size_t(sum / word_bits)] >> (sum % word_bits)) & Word(1));
    }
    return reachable;
}

// Returns the maximum subset sum not exceeding limit.
inline int subset_sum_max_value(const std::vector<int>& weights, int limit) {
    using Word = internal::SubsetSumWord;
    constexpr int word_bits = std::numeric_limits<Word>::digits;
    const std::vector<Word> bits =
        internal::subset_sum_reachability_bits(weights, limit);

    for (std::size_t i = bits.size(); i-- > 0;) {
        if (bits[i] != Word(0)) {
            return int(i * word_bits + std::bit_width(bits[i]) - 1);
        }
    }
    return 0;
}

template <typename Value = long long>
std::vector<Value> zero_one_knapsack_max_value(
    const std::vector<int>& weights,
    const std::vector<Value>& values,
    int capacity,
    Value neg_inf = std::numeric_limits<Value>::lowest() / Value(4)
) {
    assert(weights.size() == values.size());
    assert(0 <= capacity);

    std::vector<Value> dp(std::size_t(capacity) + 1, neg_inf);
    dp[0] = Value{};
    for (std::size_t item = 0; item < weights.size(); ++item) {
        const int weight = weights[item];
        assert(0 <= weight);
        for (int current = capacity; weight <= current; --current) {
            if (dp[current - weight] == neg_inf) continue;
            dp[current] = std::max(dp[current], dp[current - weight] + values[item]);
        }
    }

    for (int current = 1; current <= capacity; ++current) {
        dp[current] = std::max(dp[current], dp[current - 1]);
    }
    return dp;
}

template <typename Value = long long>
std::vector<Value> bounded_knapsack_max_value(
    const std::vector<int>& weights,
    const std::vector<Value>& values,
    const std::vector<int>& counts,
    int capacity,
    Value neg_inf = std::numeric_limits<Value>::lowest() / Value(4)
) {
    assert(weights.size() == values.size());
    assert(weights.size() == counts.size());
    assert(0 <= capacity);

    std::vector<Value> dp(std::size_t(capacity) + 1, neg_inf);
    dp[0] = Value{};

    for (std::size_t item = 0; item < weights.size(); ++item) {
        const int weight = weights[item];
        const Value value = values[item];
        const int count = counts[item];
        assert(0 <= weight);
        assert(0 <= count);
        if (count == 0) continue;

        if (weight == 0) {
            if (Value{} < value) {
                const Value gain = value * Value(count);
                for (Value& current : dp) {
                    if (current != neg_inf) current += gain;
                }
            }
            continue;
        }

        std::vector<Value> next = dp;
        for (int residue = 0; residue < weight && residue <= capacity; ++residue) {
            std::deque<int> indices;
            std::deque<Value> bases;
            int k = 0;
            for (int current = residue; current <= capacity; current += weight, ++k) {
                if (dp[current] != neg_inf) {
                    const Value base = dp[current] - Value(k) * value;
                    while (!bases.empty() && bases.back() <= base) {
                        bases.pop_back();
                        indices.pop_back();
                    }
                    bases.push_back(base);
                    indices.push_back(k);
                }

                while (!indices.empty() && indices.front() < k - count) {
                    indices.pop_front();
                    bases.pop_front();
                }
                if (!bases.empty()) {
                    next[current] = std::max(next[current], bases.front() + Value(k) * value);
                }
            }
        }
        dp.swap(next);
    }

    for (int current = 1; current <= capacity; ++current) {
        dp[current] = std::max(dp[current], dp[current - 1]);
    }
    return dp;
}

template <typename Weight = long long>
std::vector<Weight> zero_one_knapsack_min_weight_for_value(
    const std::vector<Weight>& weights,
    const std::vector<int>& values,
    int value_limit,
    Weight inf = std::numeric_limits<Weight>::max() / Weight(4)
) {
    assert(weights.size() == values.size());
    assert(0 <= value_limit);

    std::vector<Weight> dp(std::size_t(value_limit) + 1, inf);
    dp[0] = Weight{};
    for (std::size_t item = 0; item < weights.size(); ++item) {
        assert(Weight{} <= weights[item]);
        assert(0 <= values[item]);
        for (int value = value_limit; values[item] <= value; --value) {
            if (dp[value - values[item]] == inf) continue;
            dp[value] = std::min(dp[value], dp[value - values[item]] + weights[item]);
        }
    }
    return dp;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_DP_KNAPSACK_HPP

#line 1 "algo/dp/knapsack.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <deque>
#include <limits>
#include <vector>

namespace m1une {
namespace algo {

namespace internal {

using SubsetSumWord = unsigned long long;

inline std::vector<SubsetSumWord> subset_sum_reachability_bits(
    const std::vector<int>& weights,
    int limit
) {
    assert(0 <= limit);
    using Word = SubsetSumWord;
    constexpr int word_bits = std::numeric_limits<Word>::digits;

    const std::size_t bit_count = std::size_t(limit) + 1;
    std::vector<Word> bits((bit_count + word_bits - 1) / word_bits, Word(0));
    bits[0] = Word(1);

    auto trim = [&]() {
        const int extra = int(bit_count % word_bits);
        if (extra != 0) {
            bits.back() &= (Word(1) << extra) - Word(1);
        }
    };

    for (int weight : weights) {
        assert(0 <= weight);
        if (weight == 0 || limit < weight) continue;

        const std::size_t word_shift = std::size_t(weight / word_bits);
        const int bit_shift = weight % word_bits;
        for (std::size_t i = bits.size() - word_shift; i-- > 0;) {
            const Word source = bits[i];
            if (source == Word(0)) continue;
            const std::size_t target = i + word_shift;
            bits[target] |= source << bit_shift;
            if (bit_shift != 0 && target + 1 < bits.size()) {
                bits[target + 1] |= source >> (word_bits - bit_shift);
            }
        }
        trim();
    }
    return bits;
}

}  // namespace internal

inline std::vector<char> subset_sum_reachable(const std::vector<int>& weights, int limit) {
    using Word = internal::SubsetSumWord;
    constexpr int word_bits = std::numeric_limits<Word>::digits;
    const std::vector<Word> bits =
        internal::subset_sum_reachability_bits(weights, limit);

    std::vector<char> reachable(std::size_t(limit) + 1, 0);
    for (int sum = 0; sum <= limit; ++sum) {
        reachable[sum] = char((bits[std::size_t(sum / word_bits)] >> (sum % word_bits)) & Word(1));
    }
    return reachable;
}

// Returns the maximum subset sum not exceeding limit.
inline int subset_sum_max_value(const std::vector<int>& weights, int limit) {
    using Word = internal::SubsetSumWord;
    constexpr int word_bits = std::numeric_limits<Word>::digits;
    const std::vector<Word> bits =
        internal::subset_sum_reachability_bits(weights, limit);

    for (std::size_t i = bits.size(); i-- > 0;) {
        if (bits[i] != Word(0)) {
            return int(i * word_bits + std::bit_width(bits[i]) - 1);
        }
    }
    return 0;
}

template <typename Value = long long>
std::vector<Value> zero_one_knapsack_max_value(
    const std::vector<int>& weights,
    const std::vector<Value>& values,
    int capacity,
    Value neg_inf = std::numeric_limits<Value>::lowest() / Value(4)
) {
    assert(weights.size() == values.size());
    assert(0 <= capacity);

    std::vector<Value> dp(std::size_t(capacity) + 1, neg_inf);
    dp[0] = Value{};
    for (std::size_t item = 0; item < weights.size(); ++item) {
        const int weight = weights[item];
        assert(0 <= weight);
        for (int current = capacity; weight <= current; --current) {
            if (dp[current - weight] == neg_inf) continue;
            dp[current] = std::max(dp[current], dp[current - weight] + values[item]);
        }
    }

    for (int current = 1; current <= capacity; ++current) {
        dp[current] = std::max(dp[current], dp[current - 1]);
    }
    return dp;
}

template <typename Value = long long>
std::vector<Value> bounded_knapsack_max_value(
    const std::vector<int>& weights,
    const std::vector<Value>& values,
    const std::vector<int>& counts,
    int capacity,
    Value neg_inf = std::numeric_limits<Value>::lowest() / Value(4)
) {
    assert(weights.size() == values.size());
    assert(weights.size() == counts.size());
    assert(0 <= capacity);

    std::vector<Value> dp(std::size_t(capacity) + 1, neg_inf);
    dp[0] = Value{};

    for (std::size_t item = 0; item < weights.size(); ++item) {
        const int weight = weights[item];
        const Value value = values[item];
        const int count = counts[item];
        assert(0 <= weight);
        assert(0 <= count);
        if (count == 0) continue;

        if (weight == 0) {
            if (Value{} < value) {
                const Value gain = value * Value(count);
                for (Value& current : dp) {
                    if (current != neg_inf) current += gain;
                }
            }
            continue;
        }

        std::vector<Value> next = dp;
        for (int residue = 0; residue < weight && residue <= capacity; ++residue) {
            std::deque<int> indices;
            std::deque<Value> bases;
            int k = 0;
            for (int current = residue; current <= capacity; current += weight, ++k) {
                if (dp[current] != neg_inf) {
                    const Value base = dp[current] - Value(k) * value;
                    while (!bases.empty() && bases.back() <= base) {
                        bases.pop_back();
                        indices.pop_back();
                    }
                    bases.push_back(base);
                    indices.push_back(k);
                }

                while (!indices.empty() && indices.front() < k - count) {
                    indices.pop_front();
                    bases.pop_front();
                }
                if (!bases.empty()) {
                    next[current] = std::max(next[current], bases.front() + Value(k) * value);
                }
            }
        }
        dp.swap(next);
    }

    for (int current = 1; current <= capacity; ++current) {
        dp[current] = std::max(dp[current], dp[current - 1]);
    }
    return dp;
}

template <typename Weight = long long>
std::vector<Weight> zero_one_knapsack_min_weight_for_value(
    const std::vector<Weight>& weights,
    const std::vector<int>& values,
    int value_limit,
    Weight inf = std::numeric_limits<Weight>::max() / Weight(4)
) {
    assert(weights.size() == values.size());
    assert(0 <= value_limit);

    std::vector<Weight> dp(std::size_t(value_limit) + 1, inf);
    dp[0] = Weight{};
    for (std::size_t item = 0; item < weights.size(); ++item) {
        assert(Weight{} <= weights[item]);
        assert(0 <= values[item]);
        for (int value = value_limit; values[item] <= value; --value) {
            if (dp[value - values[item]] == inf) continue;
            dp[value] = std::min(dp[value], dp[value - values[item]] + weights[item]);
        }
    }
    return dp;
}

}  // namespace algo
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Knapsack Helpers
(algo/dp/knapsack.hpp)

Overview

Functions

Example

Required by

Verified with

Code

Knapsack Helpers (algo/dp/knapsack.hpp)

Overview

Functions

Example

Required by

Verified with

Code

Knapsack Helpers
(algo/dp/knapsack.hpp)