백준 12865번 "평범한 배낭"

문제

백준 12865번 평범한 배낭

---

풀이

유명한 01 배낭(01 Knapsack) 문제.

배낭 문제는 물건을 쪼개는게 가능한 Fraction Knapsack과
물건을 쪼갤 수 없는 01 Knapsack 두가지로 분류된다.

Fraction Knapsack의 경우는 가치가 큰 물건부터 선택한 후 나머지 물건을 쪼개는 방식으로 해결하는
그리디 알고리즘을 사용하며,
01 Knapsack의 경우 DP를 이용하여 문제를 해결해야 한다.

각 물건을 넣었을 때, 배낭에 담을 수 있는 무게별 가치의 최대값을 구해가는 방식으로
알고리즘을 진행시켜야한다.

물건	1	2	3	4
무게(w)	6	4	3	5
가치(v)	13	8	6	12

i = 1

i \ j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0
3	0
4	0

i = 2

i \ j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0
4	0

i번째 물건의 무게(w)가 배낭에 들어갈 수 있는 무게 j보다 클 경우 배낭에 담을 수 없으므로
i-1번 째 물건 단계에서 구했던 최댓값을 그대로 내려받는다.
dp[i][j] = dp[i-1][j]

i = 3

i \ j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0

반대로 w가 j보다 작을 경우 배낭에 담을 수 있으며,
i-1번째 물건 단계에서 구했던 남은 무게의 최대값을 더 담을 수 있게 된다.
즉, dp[i][j] = v(현재 물건의 가치) + dp[i-1][j-w]
다만 전 단계의 최댓값이 더 큰 가치를 가지고 있을 수 있다는 것을 고려해야 한다.

i = 4

i \ j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

사이클이 끝나면 위와 같은 표가 완성이 된다.

---

Python 코드

import sys

input = sys.stdin.readline

arr = []
n, k = map(int, input().split())
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
  arr.append(list(map(int, input().split())))

for i in range(1, n+1):
  for j in range(1, k+1):
    w = arr[i-1][0]
    v = arr[i-1][1]

    if (j < w):
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j]=max(v+dp[i-1][j-w], dp[i-1][j])

print(dp[n][k])