[백준] 평범한 배낭(Knapsack, DP)

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

12865번: 평범한 배낭

Dynamic Programming을 사용하는 문제입니다. 

 

문제부터 요약해보면, N개의 물건이 각각 W라는 무게와 V라는 가치를 가집니다. 이 때, 최대로 버틸 수 있는 무게 K가 주어지면, 얼마만큼의 최대 가치를 물건들을 통해 얻을 수 있는지를 return 하여야 합니다. 

이 문제는 Knapsack problem으로 유명한 문제입니다. 

 

https://en.wikipedia.org/wiki/Knapsack_problem

Knapsack problem - Wikipedia

 

올바른 solution을 먼저 제시하고, 처음에 시도했던 dfs 시간초과가 난 방법 또한 적으려 합니다.

 

<Solution-정답>

아이디어는 Dynamic programming으로 부터 비롯됩니다. 

 

간단하게 소개하면, 

N:4, K:7인 상황을 생각해봅시다. 그리고 row는 물건의번호, column은 weight을 나타낸다고 생각해봅시다. 

그러면 다음과 같은 상황이 되게 됩니다. 

이 array를 dp array라고 생각해봅시다. 이제 dp[i][j]가 의미하는 바를 정의하면 i번 물건번호까지 조회했을 시 j weight가 최대치 일때 최대 V 라고 정의합시다. 

예시로 dp[2][4]를 생각해봅시다. 그럼 2번물건까지 가방에 담을지 말지 정했을 때, 가방의 무게 최대가 4라면 최대의 value를 의미합니다.

 

그러면 이 정의로 부터 점화식을 생각 할 수 있습니다. 

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

이것이 의미하는 바는 만약 i번째 물건을 넣을지 말지 결정을 해야하는 상황이 오면, (현재의 무게상황에 i라는 물건을 넣는 것이 고려가능할 때) 

1. i-1번째 물건까지 최대 무게 j로 넣을지 말지 결정하였을 때 최대 value 2. i-1번째 물건까지 최대 무게 j-(i번째 물건무게)로 넣을지 말지 결정하였을 때 최대 value + i번째 물건의 value

이렇게 두개를 비교하여 더 큰 것을 넣어야 함을 알 수 있습니다. 각각 i번째 물건을 넣지 않는 경우, 넣는 경우라고 생각하시면 될 것 같습니다. 

그림을 이용하여 추가설명 하면, 아래 그림과 같습니다. 

이렇게 이용하면, 점화식을 진행 시킬 수 있습니다. 

for row in range(1,n+1): # object
    for col in range(1,k+1): # weight

다음과 같은 코드를 진행시키면 모든 부분에 대해 점화식이 진행되면서 각각에 대한 최댓값을 구해줍니다. 

실제 구현은 아래와 같습니다. 

import fileinput

i = 0
data = []

for line in fileinput.input():
    if i == 0: 
        temp = list(map(int,line.split()))
        n = temp[0]
        k = temp[1]
        i+=1
    else:
        data.append(list(map(int,line.split())))

# DP (Knapsack)
dp = [[0]*(k+1) for _ in range(n+1)]

for row in range(1,n+1): # object
    for col in range(1,k+1): # weight
        temp = col-data[row-1][0] 
        if temp >=0 :
            dp[row][col] = max(dp[row-1][col],dp[row-1][temp]+ data[row-1][1])
        else:
            dp[row][col] = dp[row-1][col]

print(dp[n][k])

<추가 testcase>

'''
testcase
--------------------
input
1 2
1 3

output
0
--------------------
input
10 999
46 306                          
60 311
33 724
18 342
57 431
49 288
12 686
89 389
82 889
16 289

output
4655
--------------------
'''

 

<Solution-오답>

처음 푼 dfs를 이용한 방법인데 이 경우 시간초과가 나는 것을 확인 할 수 있었습니다.

import fileinput
import copy

i = 0
data = []

for line in fileinput.input():
    if i == 0: 
        temp = list(map(int,line.split()))
        n = temp[0]
        k = temp[1]
        i+=1
    else:
        data.append(list(map(int,line.split())))
#print(data)
#print(f'n : {n}, k : {k}')
#dfs
def dfs():
    stack = [[0,0,0]] # current w, current v, current n
    answer_list = []
    while stack:
        #print(f'stack : {stack}')
        pop_data = stack.pop()
        #print(f'pop_data : {pop_data}')
        if pop_data[2] >n-1 : 
            answer_list.append(pop_data[1])
            continue

        stack.append([pop_data[0], pop_data[1], pop_data[2]+1])
        if pop_data[0]+data[pop_data[2]][0] <= k:
            stack.append([pop_data[0]+data[pop_data[2]][0], pop_data[1]+data[pop_data[2]][1], pop_data[2]+1])
        else:
            answer_list.append(pop_data[1])

    print(max(answer_list))

dfs()