トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 032

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 032 - D

  • AtCoder Beginer Contest 032 - D ナップサック問題
    • N 個の荷物があり、i番目の荷物には価値 v と重さ w が割り当てられている。
    • 許容重量 W のナップサックが1つある。
    • 重さの和が W 以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。

  解説

どうやってWを最大化するか?

  • 解説を読むとわかるのは、この問題は半分全列挙、動的計画法のどちらもわかっていないと完解できないということだ。
    • しかもdpテーブルの作成方法が蟻本の解説の応用編となる
  • 条件に注目
    • N≦30
    • N≦30 かつ w が 1 ≦ w ≦ 1000
    • N≦30 かつ v が 1 ≦ v ≦ 1000

これらを順番に

で解く。のだけど、絶賛TLE中。

  • 8/24 半分全列挙部分を解決
  • 8/26 01ナップサック問題について 蟻本 - 動的計画法 にまとめる(ただし計算量が通常版)
  • 8/28 インデックス mod2 DP, 逆順DP についての情報を得る 動的計画法における空間計算量削減テク
  • 8/30 やっとACできた、結論としてはRubyでは逆順DP使ってもACできない、コンパイル言語で計算量に気をつければ蟻本と同じようにすれば解ける

参考

  解説の解説

半分全列挙(部分点)

  • Nの個数が30以内であれば半分全列挙で最大の価値Vを計算する

手順

  1. 荷物の前半分を切り出しS1とする、荷物の後半分を切り出しS2とする
  2. S1の個数でbit全探索する
    1. bitの1/0に従って荷物をナップサックに入れたときの価値と重さを仮に計算する
    2. もし荷物の重さが上限を超えていないならば, 一時変数(tmp_a)にそのハッシュマップを加える
  3. S2の個数でbit全探索する
    1. bitの1/0に従って荷物をナップサックに入れたときの価値と重さを仮に計算する
    2. もし荷物の重さが上限を超えていないならば, tmp_a を前から検索しその重さを加算してWを超えない最初のハッシュを取得
    3. これを繰り返して最大のVを出す

ちなみに meet in the mid が半分全列挙の英訳らしい

+ 半分全列挙Rubyソース

+ 半分全列挙D言語ソース

動的計画法(完解)

たぶんRubyだと逆順DPを使わないとACできない RubyだとどうしてもTLEになるのであきらめましょう。

+ D言語 O(nΣvi)バージョン

+ D言語 O(nΣwi)バージョン

お名前: コメント: