반응형
배낭 문제 변형
배낭 문제는 여러 변형이 있습니다. 오늘은 두 가지 주요 변형인 다중 배낭 문제(Multiple Knapsack Problem)와 무제한 배낭 문제(Unbounded Knapsack Problem)에 대해 학습하겠습니다.
다중 배낭 문제 (Multiple Knapsack Problem)
다중 배낭 문제는 여러 개의 배낭이 주어졌을 때, 각 배낭에 아이템을 넣어 최대 가치를 얻는 문제입니다. 이는 기본 배낭 문제의 확장으로, 각 배낭마다 최대 용량이 다를 수 있습니다.
문제 정의
- 주어진 배낭의 수 (m)
- 각 배낭의 최대 용량 (W_i)
- 각 아이템의 무게 (w_j)와 가치 (v_j)
다중 배낭 문제 구현
다음은 C++로 다중 배낭 문제를 해결하는 예제입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int multipleKnapsack(const std::vector<int>& weights, const std::vector<int>& values, const std::vector<int>& capacities) {
int n = weights.size();
int m = capacities.size();
// DP 테이블 초기화
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(10005, 0));
// 각 배낭에 대해 DP 수행
for (int k = 1; k <= m; ++k) {
int capacity = capacities[k-1];
for (int i = 0; i < n; ++i) {
for (int w = capacity; w >= weights[i]; --w) {
dp[k][w] = std::max(dp[k][w], dp[k][w - weights[i]] + values[i]);
}
}
}
// 최대 가치 계산
int maxValue = 0;
for (int k = 1; k <= m; ++k) {
maxValue = std::max(maxValue, *std::max_element(dp[k].begin(), dp[k].end()));
}
return maxValue;
}
int main() {
std::vector<int> weights = {2, 3, 4, 5};
std::vector<int> values = {3, 4, 5, 6};
std::vector<int> capacities = {5, 10};
int result = multipleKnapsack(weights, values, capacities);
std::cout << "최대 가치: " << result << std::endl;
return 0;
}무제한 배낭 문제 (Unbounded Knapsack Problem)
무제한 배낭 문제는 각 아이템을 무한정으로 사용할 수 있는 배낭 문제입니다. 이는 각 아이템을 여러 번 사용할 수 있다는 점에서 기본 배낭 문제와 다릅니다.
문제 정의
- 주어진 배낭의 최대 용량 (W)
- 각 아이템의 무게 (w_j)와 가치 (v_j)
무제한 배낭 문제 구현
다음은 C++로 무제한 배낭 문제를 해결하는 예제입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int unboundedKnapsack(int W, const std::vector<int>& weights, const std::vector<int>& values) {
int n = weights.size();
// DP 테이블 초기화
std::vector<int> dp(W + 1, 0);
// DP 수행
for (int i = 0; i < n; ++i) {
for (int w = weights[i]; w <= W; ++w) {
dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}
int main() {
std::vector<int> weights = {2, 3, 4, 5};
std::vector<int> values = {3, 4, 5, 6};
int W = 10;
int result = unboundedKnapsack(W, weights, values);
std::cout << "최대 가치: " << result << std::endl;
return 0;
}
설명
- 다중 배낭 문제:
- 여러 개의 배낭을 가진 배낭 문제를 해결합니다.
- 각 배낭마다 최대 용량을 가지며, 각 배낭에 대해 DP를 수행하여 최대 가치를 계산합니다.
dp[k][w]는 (k)번째 배낭에서 무게 (w)를 채울 때의 최대 가치를 의미합니다.
- 무제한 배낭 문제:
- 각 아이템을 무한정으로 사용할 수 있는 배낭 문제를 해결합니다.
- 각 무게에 대해 모든 아이템을 반복적으로 고려하여 최대 가치를 계산합니다.
dp[w]는 무게 (w)를 채울 때의 최대 가치를 의미합니다.
다중 배낭 문제와 무제한 배낭 문제의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 21: 문자열 동적 계획법(Edit Distance, Longest Common Subsequence)"에 대해 학습하겠습니다.
반응형