[자료구조 및 알고리즘] 배낭 문제와 그 변형

배낭 문제(Knapsack)

배낭문제는 여러 물건이 있을 때, 특정 조건을 만족하는 조합을 구하는 문제이다. 이를테면, 물건 n개가 있고 배낭에 m 만큼 채울 수 있을 때, 최대 무게를 초과하지 않는 범위 내에서 아이템들을 담을 수 있다. 각 아이템은 1개만 사용할 수 있고, 배낭의 무게 제한을 초과하지 않도록 아이템을 선택하여 배낭에 담아야 한다. 목표는 배낭에 담은 아이템들의 가치를 최대화하는 것이다.

 

문제 정의

입력

• N: 아이템의 개수
• W: 배낭의 최대 무게
• 각 아이템에 대해
  • w_i: 아이템 i의 무게
  • v_i: 아이템 i의 가치

출력

• 배낭의 최대 무게를 초과하지 않으면서 담을 수 있는 아이템들의 가치를 최대화한 값

해결 방법

• 0/1 배낭 문제를 해결하는 일반적인 방법은 동적계획법을 사용하는 것이다. DP 테이블을 사용해서 문제를 해결할 수 있다.

알고리즘

• DP 배열 dp를 크기 W+1로 초기화하고 모두 0으로 설정
• 각 아이템에 대해 해당 아이템을 배낭에 담을 경우와 담지 않을 경우를 고려한다.
• 아이템을 담는 경우의 가치를 계산하고, 이를 DP 배열을 통해 갱신한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, W;
    cin >> N >> W;

    vector<int> weights(N), values(N);
    for (int i = 0; i < N; ++i) {
        cin >> weights[i] >> values[i];
    }

    vector<int> dp(W + 1, 0);

    for (int i = 0; i < N; ++i) {
        int weight = weights[i];
        int value = values[i];
        for (int w = W; w >= weight; --w) {
            dp[w] = max(dp[w], dp[w - weight] + value);
        }
    }

    cout << dp[W] << '\n';

    return 0;
}

 

설명

• dp[w]는 무게가 w일 때 얻을 수 있는 최대 가치를 저장한다.
• 각 아이템에 대해, 가능한 모든 무게를 역순으로 돌면서 현재 아이템을 담는 경우와 담지 않는 경우를 비교하여 최대 가치를 업데이트 한다.
• 최종적으로 배낭의 최대 무게 W에서 얻을 수 있는 최대 가치를 출력한다.

위 방식은 0/1 배낭 문제의 표준 해결 방법으로, 각 아이템을 배낭에 넣거나 넣지 않거나의 선택을 반복적으로 고려하여 최적의 해결책을 찾는다.

 

배낭 문제의 다양한 변형

배낭 문제는 다양한 변형이 있으며, 각 변형은 특정 상황이나 제약 조건을 반영한다.

 

1. 0/1 배낭 문제 (0/1 Knapsack Problem)

• 각 아이템은 1개만 사용할 수 있다. 즉, 아이템을 배낭에 넣거나 넣지 않거나의 선택만 가능하다.
• 최대 가치를 가진 아이템 집합을 찾는 것이며, 배낭의 무게 제한을 초과하지 않도록 한다.

2. 분할 배낭 문제 (Fractional Knapsack Problem)

• 아이템을 부분적으로 사용할 수 있다. 즉, 아이템의 일부만 선택할 수 있다.
• 가치 대비 무게 비율이 가장 높은 아이템부터 배낭에 담아 최대치를 얻는 것이다.
• 그리디 알고리즘을 사용하여 아이템의 가치 대비 무게 비율이 높은 것부터 선택한다.

3. 다항 배낭 문제 (Bounded Knapsack Problem)

• 각 아이템을 최대 K개까지 사용할 수 있다.
• 배낭에 담을 수 있는 최대 만족도를 찾는 것이다. 이를 해결하기 위해 이진 분할 기법을 사용하여 문제를 0/1 배낭 문제로 변환할 수 있다.

4. 다항 배낭 문제 (Bouned Knapsack Problem) 변형

• 변형 1: K가 매우 클 때, 일반적으로 이진 분할 기법을 사용하여 문제를 0/1 배낭 문제로 변환한다.
• 변형 2: K가 작을 때는 각각의 물건을 별도로 고려하여 DP 테이블을 갱신한다.

5. 무한 배낭 문제 (Unbounded Knapsack Problem)

• 각 아이템을 무한히 많이 사용할 수 있다.
• 배낭의 최대 무게를 초과하지 않으면서 최대 가치를 얻는 문제이다.
• 0/1 배낭 문제와 유사하지만, 아이템을 여러 번 사용할 수 있다는 점을 반영하여 DP 테이블을 업데이트 한다.

6. 다차원 배낭 문제 (Multi-dimensional Knapsack Problem)

• 배낭의 제약 조건이 단일 무게가 아니라 여러 제약 조건을 가진다. 예를 들어, 무게 외에 부피, 수량 등의 추가 제약 조건이 있을 수 있다.
• 여러 제약 조건을 고려하여 최대 가치를 얻어야 한다.

7. 시간 배낭 문제 (Time Knapsack Problem)

• 아이템을 선택하는 데 시간이 소요되며, 총 시간 제한이 있다.
• 주어진 시간 내에 최대 가치를 얻어야 한다.

8. 다차원 무한 배낭 문제 (Multi-dimensional Unbounded Knapsack Problem)

• 다수의 제약 조건이 있고, 아이템을 무한히 많이 사용할 수 있다.
• 모든 제약 조건을 만족하며너 최대 가치를 얻는 것이다.

9. 제한된 용량 배낭 문제 (Knapsack Problem with Capacity constraints)

• 배낭의 용량이 제한되며 특정 용량을 초과하지 않으면서 최대 가치를 얻는 문제이다.
• 용량 제약을 고려하여 최대 가치를 얻는 것이다.

10. 다중 배낭 문제 (Unbounded Knapsack Problem)

• 여러 개의 배낭이 있으며 각 배낭은 고유한 무게 제한을 가진다.
• 모든 배낭의 무게 제한을 초과하지 않으면서 최대 가치를 얻는 것이다.

예시) 무한 배낭 문제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, W;
    cin >> N >> W;

    vector<int> weights(N), values(N);
    for (int i = 0; i < N; ++i) {
        cin >> weights[i] >> values[i];
    }

    vector<int> dp(W + 1, 0);

    for (int w = 0; w <= W; ++w) {
        for (int i = 0; i < N; ++i) {
            if (weights[i] <= w) {
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }

    cout << dp[W] << '\n';

    return 0;
}

이처럼 배낭 문제는 다양한 제약 조건과 목표에 따라 여러 변형이 있으며 변형에 따라 해결 방법이 달라질 수 있다.

 

냅색 문제를 그리디 알고리즘으로 해결할 수 없는 이유

냅색 문제를 그리디 알고리즘으로 해결할 수 없는 이유는 그리디 접근 방식이 최적해를 보장하지 않기 때문이다. 특히 priority_queue를 이용한 그리디 알고리즘은 매 단계에서 당장의 최적 선택을 하지만 문제 전체를 해결할 때 최적해를 보장하지 못한다.

 

그리디 접근 방식은 매 단계에서 가장 큰 가치 대 무게 비율을 가지는 물건을 선택하는 것이다. 단계별로 나타내면 다음과 같다.

1. 물건들을 가치 대 무게 비율로 정렬한다.
2. 비율이 높은 순서대로 물건을 선택한다.
3. 현재 냅색에 담을 수 있는지 확인하고, 담을 수 있다면 담는다.
4. 더 이상 담을 수 없을 때까지 반복한다.

그리디 접근 방식의 한계

 

그리디 알고리즘은 각 단계에서 최적의 선택을 하므로 부분 문제들에 대해서는 최적해를 제공할 수 있다. 그러나 전체 문제에 대해서는 최적해를 보장하지 않는데, 이는 다음과 같은 이유 때문이다.

 

1. 비율이 아닌 절대 가치의 중요성

• 예를 들어, 물건 A의 무게가 1이고 가치가 100인 경우와 물건 B의 무게가 50이고 가치가 150인 경우를 생각해보면, 그리디 알고리즘은 무게 비율이 높은 A를 선택할 것이다.
• 하지만 전체 무게 제한이 50인 경우 물건 B를 선택하는 것이 전체 가치가 더 크므로 더 나은 선택일 수 있다.

2. 전체 무게 제한과 물건의 조합

• 물건들의 조합에 따라 최적해가 달라질 수 있다. 각 단계에서 최적의 선택이 전체적으로 최적의 결과를 보장하지 않는다.
• 예를 들어, 무게가 3이고 가치가 40인 물건 3개와 무게가 4이고 가치가 50인 물건이 있다. 무게 제한이 10인 경우 그리디 알고리즘은 무게 4인 물건을 선택할 수 있지만, 실제로는 무게 3인 물건 3개를 선택하는 것이 더 나은 결과를 가져올 수 있다.

3. 다양한 조합의 탐색 필요

• 냅색 문제는 다양한 물건들의 조합을 고려해야 최적해를 찾을 수 있다. 그리디 접근은 각 단계에서 선택을 확정하므로 다양한 조합을 충분히 탐색하지 못한다.

결론

 

냅색 문제는 DP나 분기 한정과 같은 방법을 사용해야 최적해를 찾을 수 있다. 이러한 방법들은 다양한 조합을 탐색하며 최적해를 보장할 수 있다. 그리디 알고리즘은 특정 상황에서 빠르고 간단하게 근사해를 구할 수 있지만, 최적해를 보장하지 못하므로 냅색 문제 해결에는 적합하지 않다.