練習問題

以下に定義するナップサック問題を、指定したそれぞれのやり方で解け。

	0	1	2	3	4
item	A	B	C	D	E
size	3	4	7	8	9
val	4	5	10	11	13

ナップサックのサイズは17。
1. top-down dynamic programmingを用いて、各ステップで１つずつ最適な品物を選択する方法
2. 1の方法をbottom-up dynamic programmingに書き換え
3. top-down dynamic programmingを用いて、各ステップで特定の品物を最適な個数選択する方法
4. 3の方法をbottom-up dynamic programmingに書き換え