スレ立てるまでもない質問はここで 149匹目

2018/05/18(金) 10:22:17.79

質問する前にGoogleで検索しましょう。 http://www.google.com/
プログラム・ソフトの使い方は PC 初心者板やソフトウェア板へ。
ウイルス、ハッキング・クラッキングを求めるような発言は禁止です。
Javascript は Web 制作板、CGI は Web プログラミング板へ。
業界談義、愚痴はプログラマ板へどうぞ。
ゲーム関係の話題はゲーム製作板へどうぞ。
ネタ、板とは関係の無い話題はご遠慮ください。

前スレ
スレ立てるまでもない質問はここで 148匹目
https://mevius.5ch.net/test/read.cgi/tech/1495618637/

注意「～と～はどっちの方が○いですか？」みたいなのは
このスレの粘着荒らしですので無視してください

VIPQ2_EXTDAT: checked:vvvvvv:1000:512:----: EXT was configured

2018/09/08(土) 03:07:48.41

AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。

個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。

例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが、
前半の動的計画法は貪欲法を成功させるための処方なのか？

普通の貪欲法はナップサック問題で必ずしも最適な答えを返さないよね？
現に、貪欲法しかしないコードを提出してみたら2問ほど間違えた。
動的計画法を前処理的に用いることで貪欲法を成功させる方法って知られてるの？(それがこの解法？)

動的計画法で品物の個数を min(m[i], MAX_V) としている (できる) 理由も分からない。

他の人もほとんどこの方法で解いてるから、知られてる方法なのかと思うが調べてもヒットしない。

2018/09/08(土) 08:45:43.57

プログラミング・コンテスト・チャレンジブック、第2版、2012

2-3 動的計画法に、ナップサック問題の変形が載ってる

n は個数で、W は重さの総和。
計算量O(nWW)を、O(nW)に落とす

アルゴリズムか、プログラミング・コンテストのスレに書き込めば？

2018/09/08(土) 09:11:13.03

>>879
すみません。
アルゴリズムのスレもコンテストのスレもまともに機能していないのでここで質問させてもらいました。

>>878の問題はその本に載ってる問題のバリエーションの一つで、ナップサックの容量が極めて大きいので O(nW) では TLE です。

その本では動的計画法で品物の重さの総和が i であるときの価値の総和の最大値を記録した動的計画法テーブルを作っているのですが、
>>878で述べている「前半の動的計画法」では品物の価値の総和が i であるときの重さの総和の最小値を記録したテーブルを作り、更にその後で貪欲法を適用しています。
つまり動的計画法を貪欲法のための前処理として使っていると読めるのですが、なぜそれで上手くいくのか分かりません。

2018/09/08(土) 09:18:08.58

>>880
だから数学勉強しろって
だから理解できないんだよ

2018/09/08(土) 09:27:33.16

個数の条件を外した緩和問題の解は元の問題の解の上界になるんで、それで
貪欲法の探索範囲を絞ることができる。正式には何と言うんだったか忘れたが。