せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】幅優先で解く、合計最大値問題

 
■topic summary
study about breadth first search.

 
ここを参考に。
(2/3)やわらか頭でアルゴリズムを10倍生かす - 第1回 幅優先探索の基本:ITpro

 

問題

200円持ってコンビニに行きました。コンビニには、30円、55円、66円、112円、128円、162円の6種類のお菓子があります。任意の個数のお菓子を、できるだけ合計金額が高くなるように買います。同じ種類のお菓子は1個しか買えない場合の選び方を答えなさい。

ふむふむ

 

ポイント

配列の中に配列があるときは、deepCopyを行うこと。
 
似たような「価値最大化問題」であるナップザック問題は以前に解いたところ。

 

コード

def solve(money)
     #初期状態。最大値を取るパターン=初期状態
  _solve(money, [0, []], [[0, []]])
end
def total(state)
  return 0 if state[1].length==0
  state[1].inject(:+)
end
def _solve(money, answer, que)
  #キューから要素を取り出す
  now = que.shift  
  #全キューを検査したら終了
  return answer if !now  
  #今の最大値よりも大きければ入れ替え
  answer = now if total(answer) < total(now)  
  #購入対象アイテム
  proposed = now[0]  
  #購入対象アイテムが存在する場合,次パターンをキューに詰めていく
  if FOODS[proposed]
    #購入可能な場合は購入したパターンをキューに詰める
    if (total(now) + FOODS[proposed]) <= money
      buy_pattern = Marshal.load(Marshal.dump(now))
      buy_pattern[1] << FOODS[proposed] 
      buy_pattern[0] += 1
      que << buy_pattern
    end
    not_buy_pattern = Marshal.load(Marshal.dump(now))
    not_buy_pattern[0] += 1
    que << not_buy_pattern
  end
  
  #次パターンの処理
  _solve(money, answer, que)
end

FOODS=[55, 66, 112, 128, 162, 30]
p solve(200)

 
■実行結果

[6, [55, 112, 30]]