배낭 문제(Knapsack Problem)는 유명한 동적 계획법 문제 중 하나이다. 배낭 문제가 어떻게 응용되는지 정리해보자.
배낭 문제란?
일정한 가치와 무게를 가진 짐을 담을 수 있는 최대 무게가 정해진 배낭에 담을 때, 가치의 합이 최대가 되도록 배낭에 짐을 넣는 문제이다.
배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있는데 짐을 쪼갤 수 있는 경우 그리디 알고리즘으로 해결 가능하며, 짐을 쪼갤 수 없는 경우 동적계획법으로 해결 가능하다.
완전 탐색
짐의 개수가 \(N\)개 일 때 가능한 부분집합의 개수는 \(2^N\) 개이다. 따라서 시간 복잡도는 \(O(2^N)\)이다. → 너무 느리다.
동적 계획법
$$ D[i, w] = \text{배낭의 무게 한도가 }w \text{이고 } 1 \text{번 부터 } i \text{번 짐까지 배낭에 넣을 때 얻을 수 있는 최고 가치}$$
DP 식을 위와 같이 정의했을 때 점화식은 아래와 같다.
$$ D[i,\ w] = \begin{cases} 0 & \text{if }i = 0\text{ or } w = 0 \\ D[i - 1,\ w] & \text{if }w-W_i < 0 \\ max(D[i - 1,\ w], D[i - 1,\ w - W_i] + V_i) & \text{otherwise} \end{cases} $$
반복문으로 구현하면 시간 복잡도는 \(O(NW)\)이다.
for (int i = 1; i <= N; i++){
for (int w = 0; w <= W; w++){
if (w - W[i] >= 0){
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - W[i]] + V[i]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}문제
[G5] 벼락치기
문제를 요약하면, 준석이가 공부할 수 있는 총 시간 T 동안 적절하게 K시간 단원을 공부해서 S점수를 얻을 때 얻을 수 있는 최대 점수를 구하는 것이다.
[G4] 백남이의 여행 준비
문제를 요약하면, \(K_i\) 무게만큼의 담을 수 있는 가방이 \(M\)개 있을 때 \(\frac{\text{가방에 담긴 물건의 가치의 합}}{\text{가방이 견딜 수 있는 최대 무게}}\)이 가장 작은 가방 번호를 구하는 것이다. 단순 배낭 문제에서 배낭 개수가 1개에서 \(M\)개로 변했다. 하지만 생각 없이 배낭 개수가 늘었다고 반복문을 추가해 \(O(MNW)\)에 구하면 시간 초과이다. 배낭 문제 DP 식 정의를 생각하면 배낭의 무게 한도를 가장 큰 배낭의 무게 한도로 설정하면 다른 배낭들의 답이 \(O(NW)\)에 구한 DP 배열에 모두 포함되는 것을 알 수 있다.
[G3] 앱
문제를 요약하면, 적절하게 앱을 종료해 메모리 \(m_i\)를 얻어 \(M\)바이트를 확보하고, 비용 \(c_i\)의 합을 최소화해야 한다. 배낭 문제는 최대 가치를 구하는 방법인 것을 생각하면서 주어진 문제를 배낭 문제로 바꿔 비용 \(c\)가 최대 10,000이므로 비용 \(c\)를 적절하게 지불해 얻을 수 있는 최대 메모리를 구해보자.
$$ D[i, c] = \text{최대 비용이 } c \text{일 때 } 1 \text{부터 } i \text{번째 앱을 종료할 수 있을 때 얻을 수 있는 최대 메모리} $$
DP 식을 위와 같이 정의했을 때 문제의 답은 \(M\)이상의 값을 갖는 \(D[N, c]\) 중에서 최소 \(c\)이다.
[G3] 기업투자
문제를 요약하면, 최대 투자 비용이 정해져 있을 때 각 기업에 투자했을 경우 얻게 되는 최대 이익을 구하는 문제이다. 배낭 문제로 바뀌어 생각해보자 최대 투자 비용을 가방의 최대 무게, 투자하여 얻은 최대 이익을 최대 가치로 생각한다면 배낭 문제의 정의와 일치한다. 또한 투자 비용을 쪼개어 기업에 투자할 수 없으므로 완벽한 배낭 문제이다. 그렇다면 DP 식을 아래와 같이 정의할 수 있다.
$$ D[i, j] = \text{최대 투자 비용이 } i \text{일 때 } j \text{번째 기업까지 투자했을 경우 얻을 수 있는 최대 이익} $$
[G3] 할로윈의 양아치
아이들의 친구 관계를 아래처럼 서로소 집합으로 관리하여 parent[i] = i인 아이들을 저장한 배열을 children이라하면 D[children.size()][k - 1]를 구하면 된다.
void unite(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
if(u > v) swap(u, v);
candy[u] += candy[v];
size[u] += size[v];
parent[v] = u;
}
vector<int> children;
for(int i = 1; i <= n; i++) {
if(i == parent[i]) children.push_back(i);
}
[G1] 크롬
문제를 요약하면, 적절하게 크롬 탭을 지워서 CPU와 메모리를 목표 이상 확보하려 할 때 중요도의 합의 최솟값을 구하는 것이다. 이 문제도 어떤 최솟값을 구하는 것이므로 앱 문제처럼 중요도를 배열의 인덱스로 관리해 최솟값을 구하는 방향으로 접근해보자. 앱 문제와 똑같이 DP 식을 세워보자.
D[i, p] = 최대 중요도가 p일 때 1부터 i번째 크롬 탭을 닫을 수 있을 때 얻을 수 있는 최대 cpu 사용량? 메모리? DP 식을 2차원으로 세우니 DP식 값이 최대 cpu 사용량인지 메모리인지 정할 수 없다. 따라서 구하는 값 중 1개를 인덱스로 넘겨 DP 식을 3차원으로 만들어 보자.(보통 메모리를 고려해 범위가 작은 변수를 넘겨준다.)
D[i, p, m] = 최대 중요도가 p이고, 목표 cpu 사용량이 m일 때 1부터 i번째 크롬 탭을 닫을 수 있을 때 얻을 수 있는 최대 메모리
DP 식을 위처럼 정의하면 점화식은 아래와 같다.
$$ D[i,\ p,\ m] = max(D[i - 1,\ p,\ m],\ D[i - 1,\ p - p_i,\ m - m_i] + c_i) $$
이때, \(m - m_i < 0\) 인 경우엔 cpu 사용량을 초과해서 사용한 경우인데, CPU을 목표 이상 확보하는 것이 문제이므로 \(m - m_i < 0\)경우에는 따로 분리해줘서 처리해줘야 한다.