スレ立てるまでもない質問はここで 149匹目
■ このスレッドは過去ログ倉庫に格納されています
質問する前に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 >>878-882
1. 漸化式を書く
2. DP表を描く。
dp[i][j]で、iが行・jが列で、表の後ろから埋めていく
i番目以降の品物から、重さの総和がj以下となる場合の、価値の総和の最大値
君は、1・2を書きましたか？
こういうのは数学の証明だから、難しい プログラミング・コンテスト・チャレンジブック、第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 は、重さ・価値) ■ このスレッドは過去ログ倉庫に格納されています
