0-1 ナップサック問題
(DP/knapsack_01.py)

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

概要

$0$-$1$ ナップサック問題を解く。$1$ つの袋と $N$ 個の荷物について、袋に入れる荷物の重さの合計の上限を $W$、各荷物 $i$ の価値を $v_i$、重さを $w_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\}\ ,&\quad i=1,\cdots,N.\\ \end{aligned}\]

使い方

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

Verified with

TestCase/AOJ/DPL_1_B.test.py

Code

def knapsack_01(w, items):
    dp = [-1] * (w + 1)
    dp[0] = 0

    for value, weight in items:
        for j in reversed(range(weight, w + 1)):
            if dp[j - weight] == -1:
                continue
            else:
                dp[j] = max(dp[j], dp[j - weight] + value)
    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

0-1 ナップサック問題 (DP/knapsack_01.py)

概要

使い方

Verified with

Code

0-1 ナップサック問題
(DP/knapsack_01.py)