처음에 그리디로 풀릴거 같았는데 전혀 풀리지 않았다.
알고리즘 분류를 찾아보니
- 다이나믹 프로그래밍
- 배낭 문제
이렇게 되어 있었고 "배낭 문제"가 무엇인지 찾아봤다.
💼 배낭 문제란?
배낭 문제는 n개의 물건과 각 물건 무게 Weight와 가치 Value가 주어지고, 배낭의 용량이 K일 때, 배낭용량을 초과하지 않고 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 각 물건은 하나씩만 존재한다고 가정한다.
완전 탐색과 그리디를 차례대로 떠올렸지만 전혀 풀리지 않았다.
1) 모든 경우의 수를 넣어본다(Brute-Force)
n개의 물건이 있다고 치면, n개 물건으로 만들 수 있는 가능한 부분집합 (power set) 의 수는 2^n개이다. 최악의 경우에 2^n번까지 봐야 하는, 즉 O(2^n) 의 알고리즘은 너무 느리다.
2) 무게가 가장 무거운 물건부터 넣는다(Greedy)
단위 무게당 가치를 계산하여 가장 높은것 부터 담는경우, 물건을 쪼갤 수 있는 Fractional KnapSack Problem의 경우는 최적 해를 구할 수 있지만, 통째로 담는 경우에는 반례가 너무 많아 사용할 수 없다.
그렇다면 DP로 풀어낼 수 있을까?
어떤 문제를 DP로 풀기 위해서는 아래 두가지 조건이 성립하는지 확인해야 한다.
🧐 최적의 원리(Principle of Optimality)
어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.
🧐 중복되는 부분 문제(Overlapping subproblem)
동일한 작은 문제를 반복적으로 해결한다.
이 문제에서 이 원리가 성립할까?
집합 A를 n개의 물건들 중에서 최적으로 고른 부분집합이라고 가정하자.
✅ 집합 A가 n번째 물건을 포함하고 있지 않다면
A는 n번째 물건을 뺀 나머지 n-1개의 물건들 중에서 최적으로 고른 부분집합과 같다.
✅ 집합 A가 n번째 물건을 포함하고 있다면
A는 속한 물건들의 총 가치는 n-1개의 물건들 중에서 최적으로 고른 가격의 합에다가
물건 n의 가격을 더한 것과 같다. (단, n번째 물건을 넣었을 때 가방이 터지지 않아야 한다.)
지금까지의 경우를 점화식으로 풀어보면 아래와 같다.
👩🏻💻 최종 코드
dp[i-1][j] ➡️ i번째 아이템을 배낭에 넣지 않았을 경우
i-1개의 아이템만 고려한 상태에서 배낭의 총 무게가 j일 때의 최대 가치이다.
dp[i-1][j - weight[i]] + value[i] ➡️ i번째 아이템을 배낭에 넣었을 경우
dp[i-1][j - weight[i]]는 i번째 아이템을 추가하기 전,
즉 i-1개의 아이템을 고려하고, 아직 i번째 아이템의 무게를 더할 여유가 있는 배낭의 상태를 나타낸다.
이 상태의 최대 가치에 value[i], 즉 i번째 아이템의 가치를 더하면,
i번째 아이템을 포함시켰을 때의 총 가치가 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[]args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] dp = new int[N + 1][K + 1];
int[] weight = new int[N + 1];
int[] value = new int[N + 1];
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
weight[i] = Integer.parseInt(st.nextToken());
value[i] = Integer.parseInt(st.nextToken());
}
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= K; j++) {
if(weight[i] > j) { // i번째 무게를 더 담을 수 없는 경우
dp[i][j] = dp[i-1][j];
}
else { // i번째 무게를 더 담을 수 있는 경우
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
System.out.println(dp[N][K]);
}
}
Reference
