Knapsack problem
Program
Description
これはKnapsack problemを動的計画法を用いて解くプログラムである。
ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 vi、重量 wi）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。
この問題はいくつかの点で非常に興味深い。
- 全探索（各荷物に対して持ってく or 持っていかないの2状態を列挙 ）が簡単に実装できる一方で、荷物の種類が増えると途端に計算不可能になる。 \( O ( 2 ^ n ) \)
そのほかの妥当そうに見える戦略がいずれもうまくいかない。
- 価値優先：\( 15 + 8 = 19 \)
- 個数優先：\( 2 + 3 + 1 + 4 + 8 = 18 \)
- 単位重さあたりの価値優先：\( 2 + 8 + 3 + 4 + 1 = 18 \)
- 動的計画法を用いると \( O ( n W ) \) で厳密解が求まる。
Source code
Notes
山登りをはじめたばかりのあなたは、「ひょっとして、ザックのcapacityを40Lとして、寝袋は10Lで…、このプログラムを使えばわたしのザックの中身の価値を最大化できるじゃないか！！！」と思ってしまったかもしれない。
残念ながらそれは間違っている。
必要なものはすべて持っていくべきだが、不要なものは一切持っていくべきではない。
これが登山の大原則なのである。