- 문제 링크
백준 12865번 - 평범한 배낭
해결 전략
학부 알고리즘 수업에서 0/1 Knapsack Problem에 대해 그렇게 자주 다루었음에도 불구하고 첫 번째 시도에서는 풀이에 실패하였다. 가장 큰 이유는, Dynamic Programming에 쓰이는 배열을 1차원으로 구성해 중간 중간의 아이템들의 선택 여부를 전부 고려하지 못했기 때문이었다. 즉, 0과 i 사이의 j에 대한 Optimal을 토대로 i번째 item을 함께 고려한 새로운 Optimal이 반드시 i의 Optimal이 되리란 보장이 전혀 없기 때문이었다. 단지 운 좋게 몇 가지 예시에 대해서 정답을 출력했을 뿐이었다.
과연 문제는 무엇이었을까? 중간 중간의 Optimal이 입력받은 무게 상한선 k에 대해서만 고려되었기 때문이었다. 1과 k 사이의 무게 상한에 대한 i개의 item들로 구성되는 Optimal들도 새로 고려되어야 최종적인 Optimal을 구할 수 있는 것이다.
즉, 본인이 이 문제가 DP로 어렵지 않게 해결할 수 있음을 발견했음에도, 잘못된 접근을 택해 틀린 가장 큰 이유는, 요약하면 다음과 같다고 할 수 있다.
DP에서 고려해야하는 파라미터가 2개인데, 점화식을 하나의 파라미터만을 기준으로 작성했다.
0/1 Knapsack Problem을 DP로 접근해 풀이하고자 할 때, 수식에 쓰일 수 있는 파라미터는 무엇이 있을까. 수식을 생각하지 말고, 단순히 변수로서 사용될 수 있는 요소가 무엇인지만 판단해보면, 어렵지 않게 무게, 가치, i번째 item, 무게상한 등을 떠올릴 수 있다.
이 중, 무게와 가치라는 파라미터는 i번째 item이라는 파라미터에 소속된 값이다. 따라서 파라미터를 item과 무게상한 k라고 볼 수 있게 된다.
이어서, 이 두 파라미터를 기반으로 수식을 작성해보자.
-
우선, dp[i][j]의 의미를 구성하자.
~> dp[i][j] : i-1번째 item까지 고려했을때, 무게 j를 상한으로 한 Optimal Value -
이를 "이전에 계산된 요소"로 재구성, 즉, 점화식을 설계하자.
~> dp[i][j]는, i-1번째 item을 포함시키지 않을 경우, dp[i - 1][j]와 같다.
==> 즉, default를 이 값으로 둘 수 있겠다(Idea).
~> i-1번째 item을 포함시키는 경우, dp[i - 1]j - w[i - 1]] + v[i - 1]가 곧 dp[i][j]가 될 것이다.
==> 즉, 위의 default와 이 값 중 더 큰 값을 취하면 dp[i][j]가 Optimal한 값을 가리킬 것이다.
~> i번째 인덱스에서 i - 1 번째를 체킹하고 있으므로 최종 답은 dp[n + 1][k]일 것이다. 이때, i번째 dp 배열 조회에서 i - 1을 고려하는 이유는, dp[][]값이 0인 지점을 초기값으로서 활용하기 위함이다.
위와 같은 흐름으로 수식을 설계할 수 있다. 실제로 0/1 Knapsack Problem의 DP식 해결 알고리즘은 위와 같은 방식으로 구성된다고 알려진다. 구현적인 측면에서는 어려움이 없기 때문에 여기까지만 설명하겠다.
본 문제의 교훈 : Dynamic Programming 설계 시 점화식의 파라미터가 무엇 무엇인지를 알아내는 것이 점화식 설계의 기초이자 가장 중요한 부분이다!
아래는 코드이다.
#include <iostream>
// BOJ - 12865 Normal Knapsack
using namespace std;
int w[101], v[101];
int dp[102][100001];
int solve(int n, int k) {
for (int i = 1; i <= n + 1; i++)
for (int j = 1; j <= k; j++) {
int temp = dp[i - 1][j];
if (j - w[i - 1] >= 0 && dp[i - 1][j - w[i - 1]] + v[i - 1] > temp)
temp = dp[i - 1][j - w[i - 1]] + v[i - 1];
dp[i][j] = temp;
}
return dp[n + 1][k];
}
int main(void) {
int n, k;
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
cout << solve(n, k);
return 0;
}