백준 12865번: 평범한 배낭

문제링크: 12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

 

이 문제는 제한 무게가 있는 배낭에 물품 당 무게, 가치가 각각 주어진 물품을 가장 효율적으로 넣는 문제이다. 이 문제는 DP를 활용하여 풀 수 있었다. 나는 1차원 배열의 DP를 사용해서 풀었지만 인터넷을 보니 2차원 배열의 DP를 사용해 푸는 방법도 있었다. 그런데 1차원 배열을 사용하는것이 더 간단하고 메모리나 시간복잡도 상에서도 더 좋아 보였다.

import sys

N,K=map(int,sys.stdin.readline().rstrip().split())

lst=[]
values=[0 for _ in range(K+1)]
for _ in range(N):
    lst.append(list(map(int,sys.stdin.readline().rstrip().split())))

for i in range(N): #물품 0부터 N-1까지
    w=lst[i][0]
    v=lst[i][1]
    valuescopy=values[:]
    for j in range(K):
        if j+w<=K:
            if values[j]!=0 or j==0: #가방에 뭔가 담겨져 있는 경우 또는 빈 경우
                if values[j+w]<values[j]+v:
                    valuescopy[j+w]=values[j]+v
    values=valuescopy

print(max(values))

values리스트의 각 인덱스가 물품들을 합친 무게, 값이 그 물품들의 가치 합을 뜻한다. 일단 N개의 물품 (i인덱스) 을 돌아보면서 values의 인덱스가 0일때 (빈 배낭일때)와 values의 값이 0이 아닌 인덱스(물품이 들어있을 때) j 에서 그 물품을 넣어본다. 물품을 넣었을 때의 인덱스는 j+w가 될 것이고 values[j+w]의 값이 values[j]+v 보다 작으면 동일무게 대비 물품을 넣었을 때의 가치가 더 크단 것이므로 values의 복사본인 valuescopy를 업데이트 해준다. 위 과정을 기존에 물품이 들어있던 경우 만큼 반복해 주고 그 물품 i 에 대한 탐색이 끝나면 values를 업데이트 해 준다.

 

valuescopy복사본을 만들어 준 이유는 만약 values원본을 업데이트 해 준다면 한 물품만 계속해서 넣는 경우가 생기기 때문이다. 예를들어 무게가 1, 가치가 100인 물품을 처음으로 탐색한다면 values[1]=100, 그리고 다음 반복을 통해 values[2]=200, values[3]=300 .. 이렇게 될 것이다. 처음에 이것을 생각하지 못해 오답이 되었었다. 이 풀이 방법의 특이사항은 values는 그 인덱스의 무게만큼 물품을 딱 맞게 넣었을때의 최대 가치가 저장되므로 values의 마지막 인덱스가 항상 답이 되는건 아니다. 그러므로 max(values)를 출력해 주어야 가치의 최대값이 나오게 된다.