ナップザック問題　全探索

DP_practice1.py

#引数の受け取り
n,w = map(int,input().split())
vw = [0]*n

#ビット全探索を行うために、ありうる組み合わせを全て作る
for i in range(0,n):
  vw[i] = input().split()
p = []
for i in range(2**n):
  tmp = [0]*n
  for j in range(n):
    if i >> j & 1:
      tmp[j] = 1
  p.append(tmp)
  
print(p)

#変数ｐに格納した全ての組み合わせを試す
x = []
for i in range(len(p)):
  temp = [0]*2
  for j in range(len(p[i])):
    if p[i][j] == 1:
      temp[0] += int(vw[j][0])
      temp[1] += int(vw[j][1])
  if(temp[1] <= w):
    x.append(temp[0])

print(max(x))