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

半分全列挙

[アルゴリズム]

半分全列挙

  • これはテクニックの名前であり、具体的なアルゴリズムではありません

要はすべての要素を全探索していたら時間的に間に合わないので、集合を半分ずつに分けて探索するような処理です

  半分全列挙の具体的な実装

他の人のコードリーディング

+ #607063

  • 書いたコード

+ #3063489

  • 疑似コード
N     := 荷物の数
W     := 荷物の重さ上限値

item  := { 価値 vi => 重さ wi } のハッシュマップ


S1    := item[0~N/2]  // 荷物の前半分を切り出し
tmp_a := [ { 価値 :v => 0, 重さ :w => 0 } ] のハッシュマップの配列を宣言

for (S1の個数でbit全探索) {

    bit := 1 or 0
    idx := S1のインデックス値

    tmp_h := { 価値 :v => 0, 重さ :w => 0 } を宣言

    if bit==1
        tmp_h[:v] += S1[index][:v] // 荷物をナップサックに入れたときの価値を加算
        tmp_h[:w] += S1[index][:w] // 荷物をナップサックに入れたときの重さを加算 
    end

    if tmp_h[:w] < W  // もし荷物の重さが上限を超えていないならば
        tmp_a に tmp_h を追加
    end
}

tmp_a := tmp_a を 価値の大きい順にソート
S2    := item[N/2~N]  // 荷物の後半分を切り出し
ans_v := 0             // 答え

for (S2の個数でbit全探索) {

    bit := 1 or 0
    idx := S2のインデックス値

    tmp_h := { 価値 :v => 0, 重さ :w => 0 } を宣言

    if bit==1
        tmp_h[:v] += S2[index][:v] // 荷物をナップサックに入れたときの価値を加算
        tmp_h[:w] += S2[index][:w] // 荷物をナップサックに入れたときの重さを加算 
    end

    if tmp_h[:w] < W  // もし荷物の重さが上限を超えていないならば
        x     := { tmp_a を前から検索・その重さと tmp_h[:w] を加算してWを超えない最初のハッシュを取得 }
        ans_v := ( x[:v] + tmp_h[:v] と ans_v を比べて大きいもの )
    end
}

ans_v を出力する

お名前: コメント: