個数制限付きナップサック問題
(DP/knapsack_bounded.py)

• View this file on GitHub
• Last update: 2021-05-10 23:34:32+09:00

概要

個数制限付きナップサック問題を解く。$1$ つの袋と $N$ 個の荷物について、袋に入れる荷物の重さの合計の上限を $W$、各荷物 $i$ の価値を $v_i$、重さを $w_i$、個数を $q_i$ とする。袋に入れる荷物を選ぶとき、価値の合計の最大値を求める。

以下の通りに定式化できる。

\[\begin{aligned} \max&\quad\sum_{i=1}^{N}v_ix_i&\\ \mathrm{s.t.}&\quad\sum_{i=1}^{N}w_ix_i\leq W,\\ &\quad x_i\in\{0, 1, \cdots, q_i\}\ ,&\quad i=1,\cdots,N.\\ \end{aligned}\]

使い方

knapsack_bounded(w: int, items: Iterable[Tuple[int, int, int]]) -> List[int]
荷物の重さの合計が $W_i (i = 0, \cdots, W)$ となるように、items から荷物を選んだときの最大価値のリストを返す。各荷物は (価値, 重さ, 個数) のタプルとして与える。計算量 $O(NW)$

Verified with

• TestCase/AOJ/2370.test.py
• TestCase/AOJ/DPL_1_G.test.py

Code

def knapsack_bounded(w, items):
    dp = [0] * (w + 1)
    deq = [0] * (w + 1)
    deqv = [0] * (w + 1)

    for value, weight, qty in items:
        for rem in range(weight):
            s, t = 0, 0
            j = 0
            while j * weight + rem <= w:
                val = dp[j * weight + rem] - j * value
                while s < t and deqv[t - 1] <= val:
                    t -= 1
                deq[t] = j
                deqv[t] = val
                t += 1
                dp[j * weight + rem] = deqv[s] + j * value
                if deq[s] == j - qty:
                    s += 1
                j += 1
    return dp

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page