[BOJ] 백준 12865 평범한 배낭 (Swift)

문제

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

잘 알려진 Knapsack 문제입니다.
다이나믹 프로그래밍 기법을 사용하여 풀이할 수 있습니다.

물건을 쪼갤 수 만 있다면.. 그리디 알고리즘으로도 풀리겠지만 그럴 수 없으므로
다이나믹 프로그래밍으로 풀어야 합니다.

먼저, 정의를 하자면
$f(n, k)$ = n번째 물건을 배낭에 넣으려고 하고, 배낭이 버틸 수 있는 무게가 k일 때 물건의 가치의 최대 값
입니다.

예제 입력을 살펴보면, (무게 : w, 가치 : v)의 입력이 들어옵니다.
(6, 13), (4, 8), (3, 6), (5, 12)

(6, 13) 물건을 넣을 때는 $f(1, 6)$ 부터 넣을 수 있겠네요.

행 = 물건, 열 = 무게인 표로 나타내 보겠습니다.

다음으로 2번째 물건인 (4, 8) 물건을 넣을 때를 보겠습니다.

배낭이 버틸 수 있는 무게가 6이 될 때, 2번째 물건을 빼고 1번째 물건을 넣는게 가치의 최대 값 입니다.

즉, $f(2, 6)$ 일때, $f(1, 6 - 4) = f(1, 2) + v(1)$ 입니다.
물론 2번째 물건이 가치가 더 높다면 2번 물건을 굳이 뺄 필요가 없습니다.

여기서 점화식을 도출해 낼 수 있습니다.
$f(n, k) = if\ \ k \ge w(n - 1) \ \ \ \ max(f(n - 1, k), f(n - 1, k - w(n - 1)) + v(n - 1)) \ \ \ \ else \ \ \ f(n -1, k)$

표를 전부 채우면 다음과 같이 채워집니다.

2차원 배열을 사용하지 않고 1차원 배열을 사용하는 방법도 존재합니다.

이 문제도 Well-Known 문제지만..
어떻게 풀어야 할지 고민을 많이 했던 문제입니다.