Baekjoon Training #12865

---

#12865 평범한 배낭

이 문제는 Knapsack Problem(냅색 문제)이다. 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭

가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말한다. 이때, 짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재한다.

쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem), 쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부른다. 위 문제는 쪼갤 수 없는 0-1 Knapsack의 경우이고 이는 동적계획법(Dynamic Programming)으로 풀 수 있다.

 

알고리즘

1) x축엔 가방 1~K 까지의 무게, y축은 물건 N개 개수 만큼의 배열을 만들어준다.

2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.

 

3-0) 현재 물건이 현재 돌고있는 무게보다 작다면 바로 [이전 물건][같은 무게] (knapsack[i-1][j])를 입력해준다.

3-1) 현재 물건을 넣어준다. 물건을 넣은 뒤의 남은 무게를 채울 수 있는 최댓값(knapsack[i-1][j-weight])을 위의 행에서 가져와 더해준다.

3-2) 현재 물건을 넣어주는 것보다. 다른 물건들로 채우는 값(knapsack[i-1][j])을 가져온다.

 

4) 3-1과 3-2 중 더 큰 값을 knapsack[i][j]에 저장해준다. 이 값은 현재까지의 물건들로 구성할 수 있는 가장 가치 높은 구성이다.

5) knapsack[N][K]는 곧, K무게일 때의 최댓값을 가리킨다.

 

위와 같은 방식으로 예시의 값을 이용하여 표를 채우면 아래와 같이 된다.

---

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

item = [[0,0]]
dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(n):
    item.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = item[i][0]
        v = item[i][1]
        
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)

print(dp[n][k])

위의 표를 이중 for문을 돌며 완성시키고 dp list의 맨 오른쪽 아래 값, 즉 정답을 출력해주는 코드이다.

---