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

評価関数をもつ二分探索

[アルゴリズム]

評価関数をもつ二分探索

  概要

  • 複数の品物や食塩水から、複数の対象を選んで価値や濃度を最大化する問題
    • これが難しい理由は、固定された集合に対して 二分探索 を使うのではなく、平均(or価値)の評価関数に対して 二分探索 を使うからである
  • まとめ
    • ある数列やハッシュ(以下集合と呼ぶ)が与えられたとき、K個選んで平均や価値を最大化するとする
    • ソートして最大を取ればいいじゃん→そんな簡単にできるわけないんだよなあ…→二分探索で集合を半分ずつ評価すればいい
  • やること
    • 評価関数C(x)を用意する
    • 二分探索C(x)が最大になるところを求める

  解説

  • スライドまとめ
    • 二分探索でやりたいこと
      • 解の存在範囲を半分に狭めていくことによって最適解 を求めたい!
    • どんな問題で二分探索が有効か?
      • 値の探索 (ソート済み配列、典型的な問題)
      • 最小値の最大化 (Aggressive cows)
      • 最大値の最小化 (Monthly Expense)
      • ある条件下での最大化、最小化 (Cable master, 平均最大化)
    • 終了条件は?
      • while(ub – lb > 1) パターン (配列操作、答えが整数)
      • 二分探索の回数で判定するパターン (100回やれば十分)

  問題パターン

平均最大化問題

  • 重さと価値がそれぞれw, vであるn個の品物が与えられる
  • このとき、そこからk個選んで単位重さあたりの価値が最大化したときの価値の最大値を求めよ
  • n = 3
  • k = 2
  • (w,v) ={2,2},{5,3},{2,1}

+ Rubyのコードに翻訳

最小値の最大化

最大値の最小化

お名前: コメント: