個数制限なしナップサック問題
ナップザック問題については、課題４２で説明しました。今回は個数制限なしのナップサック問題です。
「同じアイテムをいくつでも選べる」というだけで、0-1ナップサック問題と大きく異なる戦術が必要になります。「同じアイテムをいくつでも」をループとして表現してしまうと、計算量が大きくなりすぎるため避けたいところです。以下の漸化式を参考に工夫してみましょう。
Q(i, w) = \left\{
\begin{array}{ll}
0 & if \quad i = 0 \quad or \quad w = 0 \\
Q(i-1, w) & if \quad w \lt w_i \\
max \Bigl( Q (i-1, w), Q(i, 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
- 1 ≤ $W_{capacity}$ ≤ 104
とします。
- 例1
n = 3
W_capacity = 7
W = [3, 4, 2]
V = [4, 5, 3]
10
- 例2
n = 10
W_capacity = 867
W = [28, 92, 30, 1, 40, 33, 96, 30, 38, 86]
V = [6, 77, 53, 91, 47, 33, 28, 28, 78, 36]
78897
- 例3
n = 20
W_capacity = 1272
W = [10, 87, 38, 74, 19, 93, 34, 24, 63, 12, 31, 99, 45, 4, 22, 81, 50, 75, 36, 20]
V = [1, 96, 33, 97, 58, 31, 68, 60, 23, 60, 27, 7, 24, 70, 60, 73, 11, 88, 87, 71]
22260
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。