ナップザック問題
D - ナップサック問題
ビット全探索
を使って解いてみる（普通に間に合わない）
code:python
N, W = map(int, input().split())
q = [
*map(int, input().split())
for _ in range(N)]
ans = 0 # 価値の和の最大値
for i in range(1 << (N + 1)):
s, t = 0, 0
for j in range(N):
bit = i >> j
if (bit & 1) == 1:
s += q
j
1
t += q
j
0
if s > W:
break
else:
ans = max(ans, t)
continue
print(ans)