【Ruby】【アルゴリズム】幅優先で解く、合計最大値問題
■topic summary
study about breadth first search.
ここを参考に。
(2/3)やわらか頭でアルゴリズムを10倍生かす - 第1回 幅優先探索の基本:ITpro
問題
200円持ってコンビニに行きました。コンビニには、30円、55円、66円、112円、128円、162円の6種類のお菓子があります。任意の個数のお菓子を、できるだけ合計金額が高くなるように買います。同じ種類のお菓子は1個しか買えない場合の選び方を答えなさい。
ふむふむ
コード
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]]