[알고리즘] 배낭 문제에서 넣은 물건을 찾는 방법

뭘 넣었는데!

배낭 문제가 뭔지 잘 모른다면 이 글을 읽고 오자!

 

🔍  배낭 문제에서 넣은 물건을 어떻게 찾을까?

보통 배낭 문제에서는 어떤 물건을 넣었는지 보다는 가치의 최댓값을 물어보기 때문에, 해당 방식을 무조건 알지 않아도 된다고 생각한다.

하지만 내가 풀지 못했던 코딩테스트 문제에서는 내 생각에는 넣은 물건을 알아야 문제를 풀 수 있었다.

 

따라서 배낭 문제에서 넣은 물건을 찾는 방법에 대해 추가로 글을 작성하게 됐다.

 

▶️ 넣은 물건을 찾는 방법

바로 선택된 물건을 역추적 하면 된다.

설명을 위해 이전 포스팅에서 사용한 그림을 그대로 가져왔다.

• 아래 예제의 경우에는 마지막 값인 가치의 최댓값이 14이다.
  즉, 선택된 물건을 찾기 위해서는 14를 만든 물건을 역추적 하면 된다.

 

 

• 무게가 7일 때, 최댓값이 14이므로, 14를 만들어낸 물건을 찾아내면 된다.
  아래 표에서 물건이 (3, 6)일 때, 가치가 14가 됐으므로, (3, 6)을 담았다는 것을 알 수 있다.

 

• 이후에는 물건(3, 6)을 제외한 무게에서의 최댓값을 만들어낸 물건을 위와 같은 방식으로 찾아내면 된다.
  즉, 물건(3, 6)을 제외한 무게인 4(7-4)에서 최댓값인 8을 만들어낸 물건을 찾아야 한다. 따라서 물건 (4, 8)을 담았다는 것을 알 수 있다.

 

이후에는 값이 계속해서 0으로 다른 무건을 담지 않았다는 것을 의미한다. 따라서 물건 (4, 8) (3, 6)으로 2개를 담은 것이다.

 

▶️ 넣은 물건을 찾는 방법 코드 구현

N, K = map(int, input().split())

bag = []
for _ in range(N):
    w, v = map(int, input().split())
    bag.append((w, v))

dp = [[0]*(N+1) for _ in range(K+1)]

for k in range(1, K+1):
    for i in range(1, N+1):
        w, v = bag[i-1]
        if w <= k:
            dp[k][i] = max(dp[k][i-1], dp[k-w][i-1]+v)
        else:
            dp[k][i] = dp[k][i-1]

print(dp[K][N])

select_item = []

k = K
for i in range(N, 0, -1):
    if dp[k][i] != dp[k][i-1]:
        select_item.append(i-1)
        k -= bag[i-1][0]

print(select_item[::-1])