難しいナップサック問題はどこにある？

NP 困難な最適化問題の定番、みんな大好きナップサック問題の話です。話が発散しないよう、今回取り扱うのは 0-1 ナップサック問題に限ることとします。 TL; DR 理論的には NP 困難だけど、実用上ほとんどは簡単な問題 ちゃんと書いた分枝限定法ソルバーであれば、ランダムに作った問題だと n=1000 万でも 120 ミリ秒くらいで解けちゃう こうなると入出力の時間の方がボトルネック profit-weight の分布を特徴的にしたとき、難しい問題が出てくることがある 特に貪欲法対策をやられるとつらい。対策し返してないと n=100 くらいまでしか解けなくなる 難しい問題のジェネレータもあるし、生成方法も簡単なんでちゃんと考えよう はじめに 先日こんなツイートが RT で回ってきました。 これを見てこんな風に思いました。 「そうなんだよなー、みんな難しい問題の生成方法とか知らなくてランダ