アルゴリズムと計算量の問題

難易度 1教科書の例題レベル大学数学アルゴリズムと計算量

次の $4$ 個の品物から、重さの合計が $8$ 以下になるようにいくつか選ぶ。各品物は選ぶか選ばないかのどちらかで、同じ品物を $2$ 個以上選ぶことはできない。

品物	A	B	C	D
重さ	$3$	$4$	$2$	$5$
価値	$5$	$6$	$3$	$8$

品物を A, B, C, D の順に $1, 2, 3, 4$ 番目とし、 $i$ 番目の品物の重さを $w_{i}$ 、価値を $v_{i}$ とする。 $V [i] [w]$ を「 $1$ 番目から $i$ 番目までの品物だけを使い、重さの合計が $w$ 以下になるように選んだときの価値の合計の最大値」とすると、 $V [0] [w] = 0$ であり、 $i ≧ 1$ のとき
$V [i] [w] = {V [i - 1] [w] max (V [i - 1] [w], V [i - 1] [w - w_{i}] + v_{i}) (w < w_{i}) (w ≧ w_{i})$
が成り立つ。この表を $w = 0, 1, \dots, 8$ について埋め、選んだ品物の価値の合計の最大値 $V [4] [8]$ を求めよ。

この問題で使うもの

0-1 ナップサック問題の動的計画法（説明と入口の問題）

この問題を解けるようになるまで（2 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

0-1 ナップサック問題の動的計画法を使う。品物を 1 つずつ増やしながら、容量 $w = 0, \dots, 8$ ごとの最大価値 $V [i] [w]$ の表を 1 行ずつ埋めていく。

ヒント 2

$i$ 番目の品物を「選ばない」場合の $V [i - 1] [w]$ と、「選ぶ」場合の $V [i - 1] [w - w_{i}] + v_{i}$ の大きい方が $V [i] [w]$ になる。 $w < w_{i}$ のときは選べないので上の行をそのまま写す。

ヒント 3

A, B, C まで使ったときの表は $V [3] = (0, 0, 3, 5, 6, 8, 9, 11, 11)$ （ $w = 0, \dots, 8$ ）となる。最後に D（重さ $5$ 、価値 $8$ ）を加えた行の $w = 8$ の値を計算する。

答えと解説

答えを見る

13

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

漸化式に従って、表を $i = 0, 1, 2, 3, 4$ の順に 1 行ずつ埋めていく。各行は $w = 0, 1, \dots, 8$ の $9$ 個の値を並べて書く。

$i = 0$ （品物なし）：すべて $0$ 。
$V [0] = (0, 0, 0, 0, 0, 0, 0, 0, 0)$

$i = 1$ （A: $w_{1} = 3, v_{1} = 5$ ）： $w < 3$ では $V [0] [w] = 0$ 。 $w ≧ 3$ では $max (0, 0 + 5) = 5$ 。
$V [1] = (0, 0, 0, 5, 5, 5, 5, 5, 5)$

$i = 2$ （B: $w_{2} = 4, v_{2} = 6$ ）： $w < 4$ では上の行と同じ。
- $w = 4$ : $max (V [1] [4], V [1] [0] + 6) = max (5, 6) = 6$
- $w = 5$ : $max (5, V [1] [1] + 6) = max (5, 6) = 6$
- $w = 6$ : $max (5, V [1] [2] + 6) = max (5, 6) = 6$
- $w = 7$ : $max (5, V [1] [3] + 6) = max (5, 11) = 11$
- $w = 8$ : $max (5, V [1] [4] + 6) = max (5, 11) = 11$
$V [2] = (0, 0, 0, 5, 6, 6, 6, 11, 11)$

$i = 3$ （C: $w_{3} = 2, v_{3} = 3$ ）： $w < 2$ では上の行と同じ。
- $w = 2$ : $max (0, V [2] [0] + 3) = 3$
- $w = 3$ : $max (5, V [2] [1] + 3) = max (5, 3) = 5$
- $w = 4$ : $max (6, V [2] [2] + 3) = max (6, 3) = 6$
- $w = 5$ : $max (6, V [2] [3] + 3) = max (6, 8) = 8$
- $w = 6$ : $max (6, V [2] [4] + 3) = max (6, 9) = 9$
- $w = 7$ : $max (11, V [2] [5] + 3) = max (11, 9) = 11$
- $w = 8$ : $max (11, V [2] [6] + 3) = max (11, 9) = 11$
$V [3] = (0, 0, 3, 5, 6, 8, 9, 11, 11)$

$i = 4$ （D: $w_{4} = 5, v_{4} = 8$ ）： $w < 5$ では上の行と同じ。
- $w = 5$ : $max (8, V [3] [0] + 8) = max (8, 8) = 8$
- $w = 6$ : $max (9, V [3] [1] + 8) = max (9, 8) = 9$
- $w = 7$ : $max (11, V [3] [2] + 8) = max (11, 11) = 11$
- $w = 8$ : $max (11, V [3] [3] + 8) = max (11, 13) = 13$
$V [4] = (0, 0, 3, 5, 6, 8, 9, 11, 13)$

したがって $V [4] [8] = 13$ である。最後の比較で $V [3] [3] + 8$ の方を採用したので D を選んでおり、残りの容量 $3$ で $V [3] [3] = 5$ を与えるのは A である。実際に A と D を選ぶと重さ $3 + 5 = 8$ 、価値 $5 + 8 = 13$ となり確かめられる。

答え： $13$

別解

V[0][w]=0 から順に表を埋める。

i=1（A: w=3, v=5）: w=0,1,2 で 0、w=3〜8 で 5。
V[1] = [0,0,0,5,5,5,5,5,5]

i=2（B: w=4, v=6）: w<4 は V[1] と同じ。w≥4 では max(V[1][w], V[1][w-4]+6)。
w=4: max(5, 0+6)=6
w=5: max(5, 0+6)=6
w=6: max(5, 0+6)=6
w=7: max(5, V[1][3]+6=11)=11
w=8: max(5, V[1][4]+6=11)=11
V[2] = [0,0,0,5,6,6,6,11,11]

i=3（C: w=2, v=3）: w<2 は同じ。w≥2 では max(V[2][w], V[2][w-2]+3)。
w=2: max(0, 0+3)=3
w=3: max(5, 0+3)=5
w=4: max(6, 0+3)=6
w=5: max(6, 5+3)=8
w=6: max(6, 6+3)=9
w=7: max(11, 6+3)=11
w=8: max(11, 6+3)=11
V[3] = [0,0,3,5,6,8,9,11,11]

i=4（D: w=5, v=8）: w<5 は同じ。w≥5 では max(V[3][w], V[3][w-5]+8)。
w=5: max(8, 0+8)=8
w=6: max(9, 0+8)=9
w=7: max(11, 3+8)=11
w=8: max(11, V[3][3]+8=13)=13
V[4] = [0,0,3,5,6,8,9,11,13]

よって V[4][8]=13。

検算：A と D を選ぶと重さ 3+5=8、価値 5+8=13。他の組合せ：B+C=重さ6で価値9、A+B=重さ7で価値11、A+C=重さ5で価値8、B+D は重さ9で不可、C+D は重さ7で価値11、A+C+... は A+B+C で重さ9 不可。したがって最大は 13。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる