お菓子の詰め合わせ (paizaランク A 相当)：Python3解答例

お菓子の詰め合わせ (paizaランク A 相当)

背景

A 君は学校の遠足に持っていくお菓子を買わなければなりません。しかし、学校のルールにより、お菓子の総額は指定範囲内に収めなければなりません。
そこで、指定金額ギリギリまで使って、なるべく色々な種類のお菓子を食べたいと思った A 君は買うお菓子を決めるために、学校のルールと自分の要望を踏まえて以下の基準を満たす買い方をすることにしました。

・お菓子の総額を指定範囲内

・種類の数を最大にする

・同じお菓子は複数買わない

・お釣りを最小

・お釣りを最小にすることよりも種類の数を最大にすることを優先する

お菓子の値段が書いてあるリストが与えられるので、A 君の代わりに、上記ルールを満たすお菓子の組み合わせを指定範囲内の最大の金額で買ったときのお釣りを求めてください。ただし、少なくとも一種類は指定範囲の値段で買えるものとします。

入力例 1 の場合は、以下のように、指定範囲の金額で最大 2 個買えます。そして、そのうち最小になるお釣りの金額は 20 円になります。

コードの説明

combinations 関数の定義

• combinations 関数は、Python標準ライブラリの itertools.combinations と同じ機能を提供します。
• これは、与えられた iterable から r 個の要素のすべての組み合わせを生成します。
• 例えば、combinations('ABCD', 2) は ('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D') を生成します。

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

入力の読み込み

• 最初に、選択できるお菓子の種類 N と指定制限金額 money を読み込みます。
• 続けて、N 個のお菓子の値段をリスト All に格納します。

N, money = map(int, input().split())
All = []
for n in range(N):
    All.append(int(input()))
All.sort()

最大の種類数を決定する

• All リストを昇順にソートし、できるだけ多くの種類のお菓子を購入できるようにします。
• temp にお菓子の合計金額を加算し、money を超えるかどうかをチェックします。超えた場合はループを終了します。
• count は購入可能な最大の種類数を表します。

temp = 0
count = 0
for i in All:
    temp += i 
    if temp > money:
        break
    count += 1

お釣りの計算

• お菓子のリスト All から count 種類の組み合わせを生成し、それぞれの合計金額 s を計算します。
• s が money 以下であれば、money - s（お釣り）をリスト temp に追加します。

temp = []
for i in combinations(All, count):
    s = sum(i)
    if s <= money:
        temp.append(money-s)

最小のお釣りを出力

• 最後に、リスト temp の中から最小の値（最小のお釣り）を出力します。

print(min(temp))

例

入力例:

5 100
20
30
50
70
90

この場合、最適な結果として 20 が出力されます。これは、30円と50円のお菓子を選んだ場合の合計が80円で、100円からの差額（お釣り）が20円であるためです。