12865번 - 평범한 배낭(python3)

문제 링크 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

학부 알고리즘 수업 때, DP 배울 때 한 번쯤은 꼭 다뤄보는 Knapsack문제입니다. 물건을 나눌 수 있는지 없는지에 따라 푸는 방식이 달라지는데, 이 문제는 나눌 수 없는 경우의 문제입니다.(ex. 무게 4, 가치 8인 물건을 무게 1, 가치 2인 작은 물건으로 쪼개 담지 못함)

 

n개의 물건이 있고, 가방의 용량이 k라고 합시다. (k+1)*(n+1)짜리 영행렬을 만들고, 첫 번째 물건부터(n=1) 무게 w를 1부터 k까지 늘려가면서 현재 물건을 가방에 넣을 수 있는지 없는지에 따라 어떤 행동을 할 지 결정합니다.

 

n번째 물건의 무게가 현재 물건 w보다 커서 n번째 물건을 넣을 수 없다면, n-1번째 물건까지 고려했을 때의 무게 w의 상태를 가져오면 됩니다. 반면 현재의 물건을 넣을 수 있다면, "n-1번째 물건까지 고려했을 때의 무게 w의 상태"와 "현재 물건을 넣고, n-1번째 물건까지 고려했을 때의 무게 w-(n번째 물건의 무게)의 상태"를 고려해서 큰 값을 선택하면 됩니다.

 

n, w = map(int, input().split())
obj = []
for i in range(n):
    obj.append(list(map(int, input().split())))

dp = [ [0]*(w+1) for _ in range(n+1) ]

for num in range(1, n+1):
    for weight in range(1, w+1):
        if obj[num-1][0] > weight: #현재 물건을 못 넣으면
            dp[num][weight] = dp[num-1][weight] #n-1번째 물건까지 고려한 상태를 가져옴
        else: #현재 물건을 넣을 수 있으면
            dp[num][weight] = max(dp[num-1][weight], dp[num-1][weight-obj[num-1][0]]+obj[num-1][1])
            #현재 물건을 넣지 않는 것과, 현재 물건을 넣고 그 만큼의 무게를 뺀 n-1번째 물건까지 고려한 상태를 비교

print(dp[n][w])

 

DP를 워낙 오랫만에 봐서 다시 공부를 한 것도 있지만, 이번 문제를 풀면서 python으로 영행렬을 만들 때 [[0]*a]*b와 같은 꼴을 사용하면 안 된다는 사실을 배웠습니다. 제가 참고한 게시글 링크를 첨부합니다.

 

https://stackoverflow.com/questions/13157961/2d-array-of-zeros

2d array of zeros

 

1. lst = [[0]*a for _ in range(b)]

2. lst = [[0]*a]*b

 

2번과 같이 만들 경우 각 [0]*a가 같은 object이기 때문에 크기가 (8,4)인 영행렬 lst에서 lst[5][3]의 값을 1로 바꾼다고 하면, lst[0]~lst[7]의 4번째 원소가 모두 1로 바뀌는 불상사가 발생합니다. 그렇게 코드를 짜서 문제에 주어진 예제는 통과하는데 당연하게도 테스트 케이스는 통과를 못하더라구요... 직접 dp를 찍어보면서 발견한 문제점입니다. 역시 배울 게 많네요...