ナップサック問題
アイテムの集合 $I$ = {$1, 2, ..., N$} 中の各アイテム $i \in I$ の価値を $v_i$、重みを $w_i$とし、それを入れるナップサックの最大容量を $W_{capacity}$ としたとき、下記の最適化問題をナップサック問題と言います。
max \sum_{i=1}^{N} v_i x_i \\
s.t.
\sum_{i=1}^{N} w_i x_i \le W_{capacity} \\
\qquad \qquad x_i \in \mathbb{N} \qquad (\forall i \in I)
- $\in$ は英語で「in」、 $\forall$ は「for all」の意味
- $s.t.$ は「such that」の略で「下記を満たす条件の元で上記を求める」くらいの意味
- $\mathbb{N}$ は自然数全体の集合
- $x_i \in \mathbb{N}$ を $x_i \in$ {$0$, $1$} に置き換えたものを特に「0-1ナップサック問題」と言います。
ナップサック問題は「動的計画法」で解ける問題として典型的なものです。$i$番目以降$N$番目までのアイテムの中から、重さの総和が$w$以下になるように選んだ時の価値の最大値を $Q(i, w)$ としたとき、$Q(i, w)$は次のような漸化式で表せます。
Q(i, w) = \left\{
\begin{array}{ll}
0 & if \quad i = N \\
Q(i+1, w) & if \quad w \lt w_i \\
max \Bigl( Q (i+1, w), Q(i+1, w - w_i) + v_i \Bigr) & otherwise
\end{array}
\right.
基本的にはこれで解けるはずですが、同じ計算を繰り返して無駄な時間を使ってしまいます。これを避けるため、計算結果を格納する２次元配列を作って記憶することで、２度目以降の計算を省略するようにしてみましょう。
課題４２：ナップサック問題
重さが $w_i$、価値が $v_i$ である $n$ 個のアイテムがあります。これらの中から、重さの和が $W_{capacity}$ を超えない範囲内でアイテムを選んだときの、価値の和の最大値を求めてください。
ただし、同じアイテムは１個しか選べないものとし、
- 1 ≤ $n$ ≤ 100
- 1 ≤ $w_i$ ≤ 100
- 1 ≤ $v_i$ ≤ 100
- $10n$ ≤ $W_{capacity}$ ≤ $100n$
とします。
- 例1
n = 5
W_capacity = 175
W = [95, 56, 65, 54, 32]
V = [79, 9, 57, 55, 27]
139
- 例2
n = 10
W_capacity = 492
W = [53, 64, 82, 93, 76, 67, 10, 6, 82, 91]
V = [80, 16, 30, 68, 31, 19, 50, 64, 20, 96]
438
- 例3
n = 20
W_capacity = 1371
W = [30, 31, 100, 83, 52, 97, 34, 70, 96, 13, 70, 89, 79, 51, 31, 93, 73, 10, 77, 31]
V = [31, 58, 49, 75, 1, 57, 8, 1, 35, 22, 82, 28, 61, 46, 68, 10, 32, 84, 19, 16]
783
- 例４
n = 80
W_capacity = 1371
W = [7, 32, 92, 96, 96, 77, 49, 84, 80, 22, 14, 87, 4, 61, 27, 90, 23, 98, 59, 80, 25, 45, 14, 46, 41, 72, 86, 40, 27, 97, 96, 52, 86, 85, 55, 48, 92, 69, 57, 89, 2, 63, 20, 80, 98, 85, 31, 86, 65, 87, 94, 27, 95, 43, 27, 24, 65, 9, 81, 53, 36, 43, 14, 98, 85, 9, 66, 45, 49, 10, 68, 19, 5, 61, 53, 76, 75, 75, 55, 36]
V = [71, 6, 45, 90, 41, 89, 5, 57, 19, 78, 79, 100, 9, 45, 84, 41, 90, 18, 100, 34, 60, 6, 7, 82, 64, 40, 17, 44, 85, 94, 33, 90, 36, 50, 46, 66, 6, 57, 36, 4, 15, 50, 23, 94, 99, 26, 33, 95, 16, 45, 6, 93, 37, 89, 13, 52, 4, 92, 86, 10, 41, 12, 85, 43, 98, 92, 57, 38, 75, 61, 66, 1, 74, 61, 91, 33, 35, 96, 13, 17]
2604
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。