[Algorithm] Knapsack Problem

0. 문제

link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-knapsack-2/introduction

코드트리

도둑이 보석방을 털러 갔다고 하자.

(사견이지만 프로그래밍 문제에는 부도덕한 놈들이 많다..해킹하는 놈 터는 놈 등등..)

이 때 도둑 가방의 크기는 n이며, 이보다 더 무겁게 담을 수는 없다. 보석은 종류별로 단 하나씩만 있다.

도둑방에 있는 보석의 무게와 가격이 주어졌을 때, 도둑이 훔쳐올 수 있는 보석들의 가격의 합의 최대를 구하는 문제이다. 

 

1. 풀이

 

이는 동적계획법으로 해결할 수 있다. dp[i][j]를 i번째 보석까지 고려했을 때, 무게가 j일 때 담을 수 있는 최대 보석의 양으로 설정한다.

i번째 보석을 선택하느냐 선택하지 않느냐가 관건이 될 것이다. 

 

i번째 보석을 선택한 경우, 일단 i번째 보석을 넣었을 때 무게가 j인지를 검사해야 한다. 만약 넘는다면 넘어가야 한다.

넘지 않는다면, i-1번째 보석까지 고려했을 때 가방의 무게 합이 j-(i번째 보석의 무게) 일 때, 즉 dp[i-1][j-weight[i]] 에 i번째 보석을 넣었을 때의 가격이 dp[i][j]가 될 것이다. 이를 점화식으로 표현하면 다음과 같다.

 

dp[i][j] = dp[i-1][j-weight[i]] + value[i]

 

i번째 보석을 선택하지 않은 경우, dp[i][j]의 정의가 무게가 정확히 j일때의 값이므로 i-1번째 보석까지 고려했을 때 최댓값을 그대로 끌고 오면 될 것이다. 이를 점화식으로 표현하면 다음과 같다.

 

dp[i][j] = dp[i-1][j]

 

이 둘중 최댓값을 골라주면 된다. 이를 점화식으로 표현하면 다음과 같다.

 

dp[i][j] = max(dp[i-1][j-weight[i]] + value[i], dp[i-1][j])

 

2. 구현

 

weight = [3, 1, 4, 5, 2]
price = [4, 1, 2, 6, 3]
n = int(input())
dp = [[-1 for _ in range(n+1)] for _ in range(5)]

dp[0][0] = 0
dp[0][weight[0]] = price[0]

for i in range(1, 5):
    for j in range(n+1):
        if j - weight[i] >= 0 and dp[i-1][j-weight[i]] != -1:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + price[i])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(5):
    print(dp[i])

 

weight와 price가 주어진 경우로 했다. 만약 이를 다르게 하고 싶다면 그냥 입력받으면 된다.

dp의 초기화는 첫 번째 보석을 고려했을 때까지만 해준다. 이후의 값은 동적계획법으로 계산된다.