2制約ナップサックとカイジ

思っていた以上に難しい。

何が難しいかというと、速く動くプログラムの作成。

まぁ、NP困難な問題だから、そんなに簡単に速いものはつくれない。

しかし、1制約は連続緩和を利用した分枝限定法がかなり高速に動作する。

それに比べ2制約は、連続緩和が利用できない。

正しくは、利用できるが1制約のときのように簡単に解が求まらず、

高速化につながらない(むしろ悪影響か?そこは良く分からない)

どうにかして最適解の良い上界を高速に求めることができればよい。

とりあえず、現状では二つある制約のうち片方を無視して1制約だと思って連続緩和をといている。

あまり、速くない。う~ん・・・

まぁ、そんなわけで今日は 賭博黙示録カイジ を10巻まで読んだww

面白すぎるw

More Reading
Newer// カイジ
Older// HaskellでDP(2)