スレ立てるまでもない質問はここで 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(土) 18:05:51.00

>>878-882
1. 漸化式を書く
2. DP表を描く。
dp[i][j]で、iが行・jが列で、表の後ろから埋めていく

i番目以降の品物から、重さの総和がj以下となる場合の、価値の総和の最大値

君は、1・2を書きましたか？
こういうのは数学の証明だから、難しい

**888** (ﾜｯﾁｮｲ 5680-aPkH [153.177.171.243]) · 2018/09/08(土) 19:00:49.38

プログラミング・コンテスト・チャレンジブック、第2版、2012
2-3 動的計画法に、ナップサック問題の変形が載ってる

重さの総和が非常に大きい場合、1 <= W <= 10**9
O(nW)ではダメなので、DP の対象を入れ替える。
価値に対する、最小の重さを計算する

dp[i+1][j] は、i番目の品物から、価値の総和がjとなる場合の、重さの総和の最小値

1. i-1 番目の品物から、価値の総和がjとなる場合
2. i-1 番目の品物から、価値の総和がj-v[i]となるように選び、i番目の品物を加える

dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i])
(w, v は、重さ・価値)