エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
ここにツイート内容が記載されます https://b.hatena.ne.jp/URLはspanで囲んでください
Twitterで共有ONにすると、次回以降このダイアログを飛ばしてTwitterに遷移します
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
NP 困難な最適化問題の定番、みんな大好きナップサック問題の話です。話が発散しないよう、今回取り扱う... NP 困難な最適化問題の定番、みんな大好きナップサック問題の話です。話が発散しないよう、今回取り扱うのは 0-1 ナップサック問題に限ることとします。 TL; DR 理論的には NP 困難だけど、実用上ほとんどは簡単な問題 ちゃんと書いた分枝限定法ソルバーであれば、ランダムに作った問題だと n=1000 万でも 120 ミリ秒くらいで解けちゃう こうなると入出力の時間の方がボトルネック profit-weight の分布を特徴的にしたとき、難しい問題が出てくることがある 特に貪欲法対策をやられるとつらい。対策し返してないと n=100 くらいまでしか解けなくなる 難しい問題のジェネレータもあるし、生成方法も簡単なんでちゃんと考えよう はじめに 先日こんなツイートが RT で回ってきました。 これを見てこんな風に思いました。 「そうなんだよなー、みんな難しい問題の生成方法とか知らなくてランダ