『幅優先探索の基本：ITpro』の例題を解く

Python

2012/09/03
高橋　直大
出典：日経ソフトウエア　2012年7月号
やわらか頭でアルゴリズムを10倍生かす - 第1回 幅優先探索の基本：ITpro

[追記 解くと銘打ってますが間違いが多くて参考になりませんごめんなさい]

例題1

200円持ってコンビニに行きました。コンビニには、30円、55円、66円、112円、128円、162円の6種類のお菓子があります。2種類のお菓子を、合計金額が
できるだけ高くなるように買いたいとします。どんな組み合わせで買えばいいでしょうか（図1）。

解

2種類なら2重ループ総当りでいける！という直感的な話。
Pythonでリスト内包を二重にしてみたけど読みづらい。itertoolsの出番？

# -*- coding: utf-8 -*-

MONEY = 200
sweets = [30, 55, 66, 112, 128, 162]

# 2種類のお菓子の組み合わせ。200円以下。
combination = [(sweet1, sweet2) for sweet1 in sweets for sweet2 in sweets if sweet1+sweet2 <= MONEY]

# 2種類のお菓子の合算価格のうち最大値を求める
sums = map(sum, combination)
max_value = max(sums)
print max_value # => 194

# 価格が最大になる組み合わせ
max_index = sums.index(max_value)
max_pair = combination[max_index]
print max_pair # => (66, 128)

例題2

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

解

[2012.9.24 追記 幅優先できてない。アホか俺。以下間違ってるけど残しておく。]
幅優先を使わないと大変。
200円を超えない範囲でぽんぽん買い物カゴ(basket)に可能な状態を突っ込んでいく。
最大値は[30, 55, 112]の組み合わせで197円なり。
ちなみに同じ種類のお菓子を何度も買ってよい場合は[30, 30, 30, 55, 55]で200円ぴったり。

# -*- coding: utf-8 -*-

MONEY = 200
sweets = [30, 55, 66, 112, 128, 162]

# baskets - 買い物カゴの状態の配列
baskets = [[]]

# 商品の合計額が最大値になる組み合わせの配列
max_combs = []

while baskets:
    now = baskets.pop(0)
    for sweet in sweets:
        if sum(now) + sweet <= MONEY and sweet not in now:
            baskets.append(now+[sweet])
            sum_of_baskets = map(sum, baskets)
            max_comb = max(map(sum, baskets))
            max_index = sum_of_baskets.index(max_comb)
            max_comb = baskets[max_index]
    max_combs.append(max_comb)

# print max_combs[map(sum, max_combs).index(max(map(sum, max_combs)))]

ループ毎に合計額が最大となる組み合わせをmax_combとして保存しているんだけどなんか違う気がする…

[2012.10.15 訂正・追記]

コメントで教えていただいたこと。
1問目のcombinationは重複なしで選び取らなければならないので、

combination = [(sweet1, sweet2) for sweet1 in sweets for sweet2 in sweets if sweet1+sweet2 <= MONEY]

は

combination = [(sweet1, sweet2) for sweet1 in sweets for sweet2 in sweets if sweet1+sweet2 <= MONEY and sweet1 != sweet2]

でなければならない。

2問目も取り出す個数のパターン分だけcombinationを作ればいけると教えていただいた。

from itertools import combinations

MONEY = 200
sweets = [0, 30, 55, 66, 112, 128, 162]

max_combi = None
max_val = 0

for i in range(1, len(sweets)):
    combis = list(combinations(sweets, i))
    less_than_moneys = filter(lambda x: sum(x) <= MONEY, combis)
    if not less_than_moneys:
        continue
    sum_of_moneys = map(sum, less_than_moneys)
    cmax = max(sum_of_moneys)
    index = sum_of_moneys.index(cmax)
    cmax_combi = less_than_moneys[index]
    if cmax > max_val:
        max_combi = cmax_combi

print max_combi
# => (0, 30, 55, 112)

itertools.combinations使うのはずるい気がするけど…