分割ナップサック問題

C++の勉強も始まりましたが、しばらくはつまらないと思いますorz

周りに合わせるのも、必要な能力だと思いますorz

参考書借りてこよう・・・・

5kg入る袋があって、200万円で2kgのダイヤモンドと150万円で1kgのサファイアと300万円で4kgのルビーとかいろいろあったとして、どの組み合わせで入れると価値が高くなるでしょうか？

という問題がナップサック問題

分割できるとき（ダイヤモンドは1kgだけで、サファイアは4kgにしようとか）は分割ナップサック問題と言われ、

分割できないときは0-1ナップサック問題とか呼びます

分割ナップサック問題は

1, 単位重さあたりの価値が高い順に並べる

2, 単位重さあたりの価値が高いものから取り合えずある分だけ全部入れていく

3, ある分全部を入れていくと、途中できっと容量を超えるはず（ピッタリ収まることは少ないです）

4, (ナップサックの容量)-(今まで入れた総重量)だけ入れて、（まだ残っていれば）残りは入れない

結構簡単です。

（実際には配列を使ってi番目のものがどれだけ入っているかを他に保存したりする）

単位重さあたりの価値が高いものから順に入れていくのはO(n)で済みますが、単位重さあたりの価値が高い順に並べるのにソートを使うので最低でもO（nlogn）かかります

よってO（nlogn）になりますね。

0-1ナップサック問題は少し面倒

動的計画法で解く方法や、バックトラックで解く方法などがあります

また、こんどやろう