アルゴリズムクイックリファレンス 第2版

366

■

11

章 新たな分類のアルゴリズム

11.2.1

 入出力

品物（整数の重量と価値を持つ）の集合と最大重量

W

が与えられる。課題はどの

品物をナップサックに詰めれば、全重量が

W

以下で全価値が最大になるかを決定す

ることだ。

11.2.2

 文脈

これは、制約付き資源割り当て問題という種類の

1

つで、コンピュータサイエン

ス、数学、経済学でよく登場する。

1

世紀以上精力的に研究され、多数の種類がある。

最大価値だけではなく、選択した実際の品物が必要なことも多く、その解ではナッ

プサックに詰める要素も返さねばならない。

11.2.3

 解

動的計画法を用い、より単純な下位問題の結果を記憶する。

0-1

ナップサック

問

題では、最初の

i

個の品物を用いて、重量

j

を超えない最大価値の結果を、

2

次元行

列

m [i ][ j ]

に保持する。例11-1の解の構造は動的計画法で予期される二重ループに

合致している。

例

11-1

 

0-1

ナップサック問題の

Python

実装

class Item:

def __init__(self, value, weight):

"""

与えられた値と重量の品物を作る

"""

self.value = value

self.weight = weight

def knapsack_01 (items, W):

"""

対応する重量と値を持つ品物の集合に対して、

0-1

ナップサックの解を計算する（各品物が

1

つだけ使える）。

合計重量と選んだ品物を返す。

"""

n = len(items)

m = [None] ...