12865(평범한 배낭) - 실패

처음 문제를 보았을 때 가장 먼저 시도한 방법이었다. 

요즘 dfs를 사용하는것보다 itertools의 combinations 사용을 시도하고 있어서

메모리 초과가 뜨긴 했지만 정답은 도출이 되기 때문에 포스팅을 해보려 한다.

1. N과 K를 입력받으면 combination활용을 위한 index 리스트를 추가한다.

2. combination을 활용하여 나올수 있는 조합의 모든 경우의 수를 찾아낸다.

3. 각 인덱스를 활용하여 Weight가 초과되는지 초과되지 않는지를 확인한 후 초과되지 않으면 물품의 가치를 계산한다.

4. 물품의 가치가 현재 누적된 가치보다 높을 때 현재 누적된 가치를 최신화한다.

 

회고.

완전탐색으로 풀이를 하면 해결이 가능하다.

import sys
from itertools import combinations
#sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230104/12865in.txt","r")
input = sys.stdin.readline



N,K = map(int,input().split())
bag = [[0,0]]

for i in range(N):
  bag.append(list(map(int,input().split())))

index = []
for i in range(1,N+1):
  index.append(i)

answer = 0

for i in range(1,N+1):
  for k in list(combinations(index,i)):
    sum = 0 
    for t in k :
      sum += bag[t][0]
    if sum <= K: 
      weight=0
      for t in k :
          weight += bag[t][1]
      if answer < weight:
        answer = weight

print(answer)