Knapsack Limitations (個数制限付きナップサック問題)
(dp/knapsack_limitations.hpp)

• View this file on GitHub
• Last update: 2023-02-06 19:40:21+09:00
• Include: #include "dp/knapsack_limitations.hpp"

• 個数制限付きナップサック問題をスライド最大値のテクニックを使って解く
  • w : 荷物の重さ
  • v : 荷物の価値
  • m : 荷物の個数
  • W : ナップサックの容量
  • e : 価値の総和として絶対に取らない値 (普通のナップサック問題なら-1など)
  • comp : 比較関数 (最小値を求めたいときには std::less を使う)
  • s : 初期値 (普通は0だが、部分和問題などでは違うかもしれない)
• $ O(nW) $
• 部分和問題を解くために w[i] < 0 の処理も加えた

使用例

• ABC269-G
  • w[i] < 0 の処理を加えたおかげ
• ABC286-D
  • $ O \left( X \sum_{i=1}^{N} B_{i} \right) $ で通る制約なので必要ないが、$ O(XN) $ で解くなら必要

Verified with

• verify/aoj_dpl/aoj_dpl_1_g.test.cpp

Code

#pragma once

template <class T, class F = std::greater<T>>
std::vector<T> knapsack_limitations(const std::vector<int> &w, const std::vector<T> &v, const std::vector<int> &m,  //
                                    const int W, const T &e, const F &comp = F(), const int s = 0) {
    const int n = (int)w.size();
    std::vector<T> dp(W + 1, e), deqv(W + 1);
    std::vector<int> deq(W + 1);
    dp[s] = T(0);
    for (int i = 0; i < n; i++) {
        if (w[i] > 0) {
            for (int a = 0; a < w[i]; a++) {
                int s = 0, t = 0;
                for (int j = 0; a + j * w[i] <= W; j++) {
                    if (dp[a + j * w[i]] != e) {
                        T val = dp[a + j * w[i]] - j * v[i];
                        while (s < t and comp(val, deqv[t - 1])) t--;
                        deq[t] = j;
                        deqv[t++] = val;
                    }
                    if (s < t) {
                        dp[a + j * w[i]] = deqv[s] + j * v[i];
                        if (deq[s] == j - m[i]) s++;
                    }
                }
            }
        } else if (w[i] < 0) {
            for (int a = 0; a < -w[i]; a++) {
                int s = 0, t = 0;
                for (int j = 0; W - a + j * w[i] >= 0; j++) {
                    if (dp[W - a + j * w[i]] != e) {
                        T val = dp[W - a + j * w[i]] - j * v[i];
                        while (s < t and comp(val, deqv[t - 1])) t--;
                        deq[t] = j;
                        deqv[t++] = val;
                    }
                    if (s < t) {
                        dp[W - a + j * w[i]] = deqv[s] + j * v[i];
                        if (deq[s] == j - m[i]) s++;
                    }
                }
            }
        } else {
            // w[i] = 0
            continue;
        }
    }
    return dp;
}

#line 2 "dp/knapsack_limitations.hpp"

template <class T, class F = std::greater<T>>
std::vector<T> knapsack_limitations(const std::vector<int> &w, const std::vector<T> &v, const std::vector<int> &m,  //
                                    const int W, const T &e, const F &comp = F(), const int s = 0) {
    const int n = (int)w.size();
    std::vector<T> dp(W + 1, e), deqv(W + 1);
    std::vector<int> deq(W + 1);
    dp[s] = T(0);
    for (int i = 0; i < n; i++) {
        if (w[i] > 0) {
            for (int a = 0; a < w[i]; a++) {
                int s = 0, t = 0;
                for (int j = 0; a + j * w[i] <= W; j++) {
                    if (dp[a + j * w[i]] != e) {
                        T val = dp[a + j * w[i]] - j * v[i];
                        while (s < t and comp(val, deqv[t - 1])) t--;
                        deq[t] = j;
                        deqv[t++] = val;
                    }
                    if (s < t) {
                        dp[a + j * w[i]] = deqv[s] + j * v[i];
                        if (deq[s] == j - m[i]) s++;
                    }
                }
            }
        } else if (w[i] < 0) {
            for (int a = 0; a < -w[i]; a++) {
                int s = 0, t = 0;
                for (int j = 0; W - a + j * w[i] >= 0; j++) {
                    if (dp[W - a + j * w[i]] != e) {
                        T val = dp[W - a + j * w[i]] - j * v[i];
                        while (s < t and comp(val, deqv[t - 1])) t--;
                        deq[t] = j;
                        deqv[t++] = val;
                    }
                    if (s < t) {
                        dp[W - a + j * w[i]] = deqv[s] + j * v[i];
                        if (deq[s] == j - m[i]) s++;
                    }
                }
            }
        } else {
            // w[i] = 0
            continue;
        }
    }
    return dp;
}

Back to top page