競技プログラミングにハマるプログラマのスレ 17at PROG競技プログラミングにハマるプログラマのスレ 17 - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このスレッドのURL■項目テキスト109:仕様書無しさん 18/11/05 22:47:20.49 .net 舌切り雀を思い出し大きいつづらを選ぶ貪欲ババア法とでも覚えておけばOK 110:仕様書無しさん 18/11/05 22:53:26.62 .net 競プロのアドベントカレンダーというのがあるらしい https://twitter.com/-/status/1059424794892890113 111:仕様書無しさん 18/11/06 00:26:52.68 .net よくわからんから例題を挙げて貪欲法と動的計画法での解法を述べてくれぇ 112:仕様書無しさん 18/11/06 00:33:11.19 .net ナップザック問題? 113:仕様書無しさん 18/11/06 00:56:43.21 .net ん? 全探索と貪欲法の違いの話じゃなかったのか? 114:仕様書無しさん 18/11/06 01:31:07.17 .net [PDF] ナップザック問題に対する動的計画法と貪欲法の比較 An Comparative ... www.salesio-sp.ac.jp/papers/sotsuken/2012/pdf/documents/cs/5407.pdf 115:仕様書無しさん 18/11/06 03:14:55.15 .net ナップサック問題(重さの総和が一定以内で価値の総和を最大化)で言うと 貪欲: まだ積んでない荷物の中で 価値/重さ が最大の物(コスパが良いやつ)を優先して選ぶ (最適とは限らない) 動的計画法: DP[i][W] := i番目までの荷物の中から重さの総和がW(以下)になるように積んだときの最大の価値 全探索: 積むか積まないか2^N通り全部試して重さ制約を満たす中で一番いいやつ それぞれ O(NlogN), O(NW), O(2^N) 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch