背景
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円であるためです。