自己紹介
僕のX：
https://x.com/e4h99rhQ7I24670
この記事でおかしなところがあれば教えてください。
問題 お菓子の詰め合わせ (paizaランク A 相当）
感想
ビット計算、論理演算等知っていると楽だと思います。^^
知らないとかなり難しく感じるかもしれません
AtcoderだとB問題、diff200程度かなー
解説
この問題の肝はNの制約が厳しすぎるところです。(N <= 20)
この条件であれば、2^Nまで計算できます。
よって、とりあえず2^Nの計算オーダーの解法を考えればいいです。
一つのお菓子に対して買うか買わないかの二択である点から、全探索が2^Nのオーダーで計算できます。
実装で用いている計算方法
左シフト
1 << A
2^A乗の値を返す
論理積
A & B
A,Bどちらも１なら１を返す。それ以外は０を返す。
以下実装
N, X = map(int, input().split())
A = [int(input()) for _ in range(N)]
ans_money = 1 << 60
ans_num = 0
for i in range(1 << N):
num = 0
money = X
for j in range(N):
if i & (1 << j) == (1 << j):
num += 1
money -= A[j]
if money < 0:
continue
if ans_num < num:
ans_num = num
ans_money = money
elif ans_num == num:
ans_money = min(ans_money, money)
print(ans_money)