7-5. 그리디: 0/1 배낭 문제 (비교)

1. 0/1 배낭 문제와 분할 가능 배낭 문제의 비교

배낭 문제(Knapsack Problem)는 조합 최적화 문제의 대표적인 예시로, 주어진 용량의 배낭에 가장 가치 있는 물건들을 담는 방법을 찾는 문제입니다. 이 문제는 다양한 변형을 가지고 있으며, 그중 가장 기본적인 두 가지 형태가 있습니다.

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

0/1 배낭 문제는 물건을 통째로 배낭에 넣거나, 넣지 않거나 두 가지 선택만 가능한 문제입니다. 즉, 물건을 쪼개서 일부만 넣는 것은 허용되지 않습니다. 이 제약 때문에 0/1 배낭 문제는 비교적 풀기 어렵습니다. 예를 들어, 다이아몬드, 금괴, 팔찌 세 가지 물건이 있고 배낭의 용량이 제한되어 있다면, 각 물건을 전부 넣거나, 아예 넣지 않거나 둘 중 하나를 선택해야 합니다.

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

분할 가능 배낭 문제는 물건을 쪼개서 일부만 배낭에 넣을 수 있다는 점이 0/1 배낭 문제와 다릅니다. 예를 들어, 금괴가 있는데 배낭 용량의 제한으로 금괴 전체를 넣을 수 없다면, 금괴의 일부분만 잘라서 넣을 수 있습니다. 분할 가능 배낭 문제는 그리디 알고리즘을 사용하여 효율적으로 해결할 수 있습니다.

2. 그리디 알고리즘과 0/1 배낭 문제

그리디 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다. 하지만 0/1 배낭 문제에서는 그리디 알고리즘을 적용할 수 없습니다.

1) 그리디 알고리즘의 문제점

0/1 배낭 문제에 그리디 알고리즘을 적용하는 것은 최적의 해를 보장하지 못합니다. 예를 들어, 무게는 크지만 가치가 낮은 물건과, 무게는 작지만 가치가 높은 물건이 있을 경우, 그리디 알고리즘은 가치/무게 비율이 높은 물건을 먼저 선택하려 할 것입니다. 하지만 이 방식은 배낭의 용량을 효율적으로 사용하지 못해, 전체 가치가 낮은 결과를 초래할 수 있습니다.

예시:

배낭 용량: 10kg

물건 1: 무게 7kg, 가치 42원 물건 2: 무게 3kg, 가치 12원 물건 3: 무게 4kg, 가치 40원

그리디 알고리즘 (가치/무게 비율 기준):

1. 물건 3 (가치/무게 = 10) 선택: 배낭 용량 6kg 남음
2. 물건 2 (가치/무게 = 4) 선택: 배낭 용량 3kg 남음
3. 남은 공간에 다른 물건을 넣을 수 없음

총 가치 12 + 40 52원

하지만, 물건 1과 물건 2를 선택하면 (42 + 12) = 54원으로 더 높은 가치를 얻을 수 있습니다.

2) 그리디 알고리즘 적용 불가 이유

0/1 배낭 문제에서 그리디 알고리즘이 실패하는 주된 이유는 "미래를 고려하지 않기" 때문입니다. 각 단계에서 가장 좋아 보이는 선택을 하지만, 이 선택이 이후의 선택에 영향을 미쳐 전체적인 최적 해를 방해할 수 있습니다. 0/1 배낭 문제는 부분 최적 해(local optimum)가 전체 최적 해(global optimum)로 이어지지 않는 전형적인 예시입니다.

3) 해결 방법: 동적 프로그래밍 (Dynamic Programming)

0/1 배낭 문제는 동적 프로그래밍을 사용하여 해결해야 합니다. 동적 프로그래밍은 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 이용하여 더 큰 문제를 해결하는 방식입니다. 모든 가능한 물건의 조합을 고려하여 배낭에 넣을 수 있는 최대 가치를 계산하므로, 최적의 해를 보장합니다.

3. 분할 가능 배낭 문제와 그리디 알고리즘

분할 가능 배낭 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다.

1) 그리디 알고리즘 적용 가능성

분할 가능 배낭 문제에서는 물건을 쪼개서 넣을 수 있으므로, 각 물건의 가치/무게 비율을 기준으로 정렬한 후, 비율이 높은 물건부터 배낭에 넣으면 됩니다.

2) 알고리즘

1. 각 물건의 가치/무게 비율을 계산합니다.
2. 가치/무게 비율을 기준으로 물건을 내림차순으로 정렬합니다.
3. 정렬된 순서대로, 배낭에 물건을 넣습니다.
   • 물건 전체를 넣을 수 있다면, 넣습니다.
   • 물건 전체를 넣을 수 없다면, 남은 공간에 맞게 물건을 쪼개서 넣습니다.

3) 예시

배낭 용량: 50kg

물건 A: 무게 10kg, 가치 60원 (가치/무게 = 6) 물건 B: 무게 20kg, 가치 100원 (가치/무게 = 5) 물건 C: 무게 30kg, 가치 120원 (가치/무게 = 4)

1. 가치/무게 비율 계산 및 정렬: A > B > C
2. 물건 A (10kg)를 넣음: 배낭 용량 40kg 남음
3. 물건 B (20kg)를 넣음: 배낭 용량 20kg 남음
4. 물건 C의 20kg을 넣음: 배낭이 가득 참

총 가치 60 + 100 + (120 * (20/30)) 60 + 100 + 80 = 240원

4) 그리디 알고리즘의 유효성

분할 가능 배낭 문제에서 그리디 알고리즘이 최적 해를 보장하는 이유는, 물건을 쪼개서 넣을 수 있기 때문에, 각 단계에서 가장 가치 있는 부분을 선택하는 것이 전체적인 최적 해로 이어진다는 것을 보장하기 때문입니다.

4. 결론

0/1 배낭 문제와 분할 가능 배낭 문제는 모두 배낭 문제의 변형이지만, 해결 방법은 완전히 다릅니다. 0/1 배낭 문제는 그리디 알고리즘을 사용할 수 없으며, 동적 프로그래밍을 통해 해결해야 합니다. 반면, 분할 가능 배낭 문제는 그리디 알고리즘을 사용하여 효율적으로 해결할 수 있습니다. 이 차이점은 문제의 제약 조건(물건을 쪼갤 수 있는지 여부)에 따라 알고리즘 선택이 달라진다는 것을 보여줍니다.