[백준] 12865 평범한 배낭, Knapsack Problem

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

12865번: 평범한 배낭

 

유형 : DP, Knapsack Algorithm 

작년 알고리즘 수업시간에 배웠던 Knapsack Problem 과 동일한 문제이다 !!

원래 유래는 도둑이 물건을 훔칠때 들 수 있는 무게는 한정되어 있는 상황에서 최대한의 가치를 가방에 넣을 수 있는 방법을 구하는 것이었다. 

Knapsack Algorithm은 0-1 배낭 문제, 분할가능 배낭 문제 두가지 유형이 있다. 

도둑이 훔칠 물건이 분할 가능한지 vs 분할 가능하지 않은지에 따라서 나뉘는데, '평범한 배낭' 문제는 물건들이 분할되지 않으므로 0-1 배낭문제에 해당한다. 왜 0-1인가?? 물건을 담는경우가 1, 물건을 담지 않는 경우가 0 이라는 의미에서 선택지가 두 가지 뿐이기 때문이다.

담을 물건들이 총 n개이고, 배낭 안에 넣을 수 있는 무게는 총 k라고 하자. 문제의 예제로 생각해보자. 

현재 배낭이 버틸 수 있는 무게는 7이다. 

무게	6	4	3	5
가치	13	8	6	12

물건을 1개까지 확인했을 때 , 물건 1의 무게는 6이므로 배낭이 버틸 수 있는 무게 7보다 작다. 따라서 최대 가치는 13이 된다. 

물건을 2개까지 확인했을 때도, 물건 2를 드는 것보다 물건 1을 드는 것이 더 가치가 높다. 

물건 3개까지 확인했을 때는 최대 가치가 달라진다 ! 물건 2와 물건 3을 드는 것이 가치가 14이므로, 최대 가치가 된다. 

즉, dp[n][k] 는 n 번째 물건까지 확인했을 때의 들 수 있는 물건들의 최대 가치 합이되면, 문제를 풀 수 있다.

  또한 경우의 수를 따져보면 다음과 같다. 

A. 현재 확인 중인 물건을 들었을 때 k 를 넘는다면 -> 현재 물건은 넣을 수 없다. 따라서 선택지는 하나이다. 

이전 물건을 확인했을 때 (n-1번째 물건) 까지의 최대가치가 그대로 n번째에도 최대가치가 된다. 

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

B. 현재 확인 중인 물건을 들었을 때 k 를 넘지 않는다면 -> 현재 물건을 넣는다 vs 현재 물건을 넣지 않는다 라는 두가지 선택지가 있다. 

현재 물건을 넣는 경우 : dp[i-1][j - weight] + value 

weight 는 현재 확인 중인 물건의 무게, value는 현재 확인 중인 물건의 가치이다. 

현재 물건을 넣지 않는 경우 : dp[i-1][j] (n-1번째의 최대 가치가 n번째에도 최대 가치가 되는 경우이다.)

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

# 12865 평범한 배낭
n, k = map(int, input().split())
data = [[0, 0]]
for _ in range(n):
    data.append(list(map(int, input().split())))
result = 0
dp = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, k+1): # 남은 무게
        weight = data[i][0]
        value = data[i][1]
        if weight > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-weight] + value, dp[i-1][j])

print(dp[-1][-1])