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

$V[i][w]$ の表を $i=0$ の行から順に、$w=0,1,\dots ,8$ について埋めていきます。

$i=0$（品物なし）：すべての $w$ で $V[0][w]=0$ です。

$i=1$（A：重さ $3$、価値 $4$）：$w<3$ では A を入れられないので $0$。$w\ge 3$ では $\max (0,0+4)=4$。
$$V[1][w]:0,0,0,4,4,4,4,4,4$$

$i=2$（B：重さ $4$、価値 $5$）：$w\le 3$ は $V[1][w]$ をそのまま写します。
- $w=4$：$\max (V[1][4],V[1][0]+5)=\max (4,5)=5$
- $w=5$：$\max (4,V[1][1]+5)=\max (4,5)=5$
- $w=6$：$\max (4,V[1][2]+5)=\max (4,5)=5$
- $w=7$：$\max (4,V[1][3]+5)=\max (4,9)=9$
- $w=8$：$\max (4,V[1][4]+5)=\max (4,9)=9$
$$V[2][w]:0,0,0,4,5,5,5,9,9$$

$i=3$（C：重さ $2$、価値 $3$）：$w\le 1$ は $0$ のまま。
- $w=2$：$\max (0,V[2][0]+3)=3$
- $w=3$：$\max (4,V[2][1]+3)=\max (4,3)=4$
- $w=4$：$\max (5,V[2][2]+3)=\max (5,3)=5$
- $w=5$：$\max (5,V[2][3]+3)=\max (5,7)=7$
- $w=6$：$\max (5,V[2][4]+3)=\max (5,8)=8$
- $w=7$：$\max (9,V[2][5]+3)=\max (9,8)=9$
- $w=8$：$\max (9,V[2][6]+3)=\max (9,8)=9$
$$V[3][w]:0,0,3,4,5,7,8,9,9$$

$i=4$（D：重さ $5$、価値 $7$）：$w\le 4$ は $V[3][w]$ をそのまま写します。
- $w=5$：$\max (7,V[3][0]+7)=\max (7,7)=7$
- $w=6$：$\max (8,V[3][1]+7)=\max (8,7)=8$
- $w=7$：$\max (9,V[3][2]+7)=\max (9,10)=10$
- $w=8$：$\max (9,V[3][3]+7)=\max (9,11)=11$
$$V[4][w]:0,0,3,4,5,7,8,10,11$$

よって $V[4][8]=11$ です。これは $V[3][3]+7$ から来ており、$V[3][3]=4$ は A だけを選んだ場合なので、最適な選び方は A と D（重さ $3+5=8$、価値 $4+7=11$）です。

なお、重さあたりの価値が大きい順（C, D, A, B）に貪欲に入れると C と D（価値 $10$）で止まってしまい、最大値にはなりません。表を埋める動的計画法なら確実に最大値が求まります。

答え：$11$

品物は A(重さ3,価値4)、B(4,5)、C(2,3)、D(5,7)。漸化式で表を w=0,…,8 について埋める。

$V[0][w]=0$。

i=1(A: 3, 4): w=0,1,2 は 0、w=3〜8 は 4。
$V[1]=[0,0,0,4,4,4,4,4,4]$

i=2(B: 4, 5): w<4 は $V[1][w]$ と同じ。
w=4: max(4, V[1][0]+5=5)=5
w=5: max(4, V[1][1]+5=5)=5
w=6: max(4, V[1][2]+5=5)=5
w=7: max(4, V[1][3]+5=9)=9
w=8: max(4, V[1][4]+5=9)=9
$V[2]=[0,0,0,4,5,5,5,9,9]$

i=3(C: 2, 3):
w=0,1: 0, 0
w=2: max(0, V[2][0]+3=3)=3
w=3: max(4, V[2][1]+3=3)=4
w=4: max(5, V[2][2]+3=3)=5
w=5: max(5, V[2][3]+3=7)=7
w=6: max(5, V[2][4]+3=8)=8
w=7: max(9, V[2][5]+3=8)=9
w=8: max(9, V[2][6]+3=8)=9
$V[3]=[0,0,3,4,5,7,8,9,9]$

i=4(D: 5, 7):
w=0〜4: 0,0,3,4,5
w=5: max(7, V[3][0]+7=7)=7
w=6: max(8, V[3][1]+7=7)=8
w=7: max(9, V[3][2]+7=10)=10
w=8: max(9, V[3][3]+7=11)=11
$V[4]=[0,0,3,4,5,7,8,10,11]$

よって $V[4][8]=11$。

検算: 選び方は A+C+D? 重さ3+2+5=10 で超過。A+D=8 で価値 11。B+C=6 で 8、A+B=7 で 9、A+C=5 で 7、C+D=7 で 10、B+D は 9 で超過。3 個以上は A+B+C=9 超過など不可。最大は A+D の 11 で一致。