[DP][Algorithm] Knapsack Algorithm. 백준 12865 평범한 가방

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

     냅색알고리즘이라고 불리는 이 유명한 문제는 다음과 같다. 가방에 가치를 극대화하도록 물건들을 담아야 한다. 이 때 가방은 특정 무게 이상을 담을 수 없다. 제한된 K kg의 이하의 물건들을 담을 수 있다. 물건들은 (Weight, Value)로 무게와 가치라는 원소를 가지고 있다. 우리는 물건의 후보들이 담긴 array에서 가치(value)를 극대화하도록 가방에 물건을 담아야 한다. 다만, 이 문제는 위는 냅색 알고리즘 중에서도 후보 물건들을 쪼갤 수 없는 문제(unfractional knapsack problem)에 해당한다.

이 문제는 동적계획법(Dynamic programming)의 일종이라고 볼 수 있다. 가방에 있는 물건들을 K kg 이하로 조합해서 담은 다음 그것의 가치들을 계산한 뒤, 0~K kg을 넣었을 때의 각각의 최대 가치값을 저장하여 최적값을 구할 수 있기 때문이다.  

그렇다면, 어떻게 각각의 물건들을 담아서 조합한 뒤 최대 가치값을 어떤 형태로 저장해야 할까? 문제에서 단위가 소수점이 아닌 정수형태로 kg가 주어지므로, 다음과 같이 표현했다. 0부터 K까지의 무게를 담았을 때의 최대가치를 담은 배열을 만들었다. 초기값은 당연히 0이다.

possible = [0 for i in range(K+1)]

input정보이다. K = 7, stuff_array = [(6,13), (4,8), (3,6), (5,12)]

K는 담을 수 있는 최대의 물건의 무게이고, stuff_array는 (물건의 무게, 물건의 가치)를 튜플로 담은 배열이다. stuff_array의 물건을 차례대로 넣으면서, 기존의 possible에 담긴 값들과 비교하면서(각각의 0~K까지의 weight 별 최대가치를 담은 배열) 현재의 물건을 기존의 물건과 조합했을 때 최대값을 구해 possible값을 갱신한다.

아래의 전체 코드를 보면, max(possible[j], possible[j-stuff_array[i][0]]+stuff_array[i][1]) 부분의 대한 해석은 다음과 같다.

possible[j-stuff_array[i][0]]는 현재 회차의 물건stuff_array[i][0]의 무게를 뺐을 때의 possible값의 최대가치에 현재 stuff_array[i][1]가치를 더하면,possible[j]의 최대값을 기존의 값과 비교하여 갱신할 수 있다.

possible = [0 for i in range(K+1)]

for i in range(len(stuff_array)):
    for j in range(K, 1, -1):
        if bag[i][0] <= j:
            possible[j] = max(possible[j], possible[j-stuff_array[i][0]] + stuff_array[i][1])

 

    한편, 본 문제를 나는 초기에 다음과 같은 방식으로 접근하여 실패하였다. 물건리스트를 무게순으로 내림차순으로 정렬한 뒤에 앞에서부터 차례대로 가방에 처음 담는다고 생각했다. 그 다음에, 가장 작은 값을 담고 있는 리스트의 마지막 부분부터 차례대로 가방에 담은 뒤, Kg를 넘는 경우에는 해당 물건의 물건담기를 break했다. 동시에 각각의 가치들을 차곡차곡 answer에 추가하였다. 하지만, 이 경우에는 뒷부분 리스트 원소부터 차례대로 넣기 때문에 모든 가능한 경우의 수를 탐색하기가 힘들어진다. 

=> 실패한 코드는 다음과 같다. 

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

for i in range(N):
    w, v = map(int, input().split())
    stuff.append((w,v))


def final(stuff, K):
        
    
    possible = []
    stuff.sort(key=lambda x:x[0], reverse=True)

    
    for i in range(len(stuff)):
        w, v = stuff[i][0], stuff[i][1]
         
        if w <= K:
            possible.append(v)
            
        for j in range(len(stuff)-1, i, -1):
            w += stuff[j][0]
            
            if w > K:
                break
            else:
                v += stuff[j][1]
                possible.append(v)
    #print(possible)
    return max(possible)

print(final(stuff, K))