분할 가능한 배낭 문제
분할 가능한 배낭 문제란
물건을 쪼개서 담을 수 있는 배낭 문제다. 금가루, 액체 같은 연속적인 물건을 다루는 경우로, 그리디 알고리즘으로 해결 가능하다.
알고리즘 시각화
동작 예시
아래와 같은 입력이 주어졌을 때 분할 배낭 알고리즘의 동작 과정을 살펴보자.
- 배낭 용량: 50kg
- 물건 목록:
- 1번: 무게 10kg, 가치 60 (단위가치: 6.0)
- 2번: 무게 20kg, 가치 100 (단위가치: 5.0)
- 3번: 무게 30kg, 가치 120 (단위가치: 4.0)
1단계: 정렬
단위 가치(가치/무게) 기준 내림차순 정렬
정렬 결과: 1번(6.0) → 2번(5.0) → 3번(4.0)
2단계: 선택
| 단계 | 선택 물건 | 담는 양 | 가치 | 남은 용량 |
|---|---|---|---|---|
| 초기 | - | - | 0 | 50kg |
| 1 | 1번 (6.0) | 10kg 전체 | 60 | 40kg |
| 2 | 2번 (5.0) | 20kg 전체 | 100 | 20kg |
| 3 | 3번 (4.0) | 20kg (30kg 중) | 80 | 0kg |
3단계: 완성
- 1번 물건: 10kg 전체 담기 → 가치 60
- 2번 물건: 20kg 전체 담기 → 가치 100
- 3번 물건: 30kg 중 20kg만 담기 → 가치 80 (120 × 20/30)
- 최대 가치 합: 240
복잡도
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 시간 복잡도 | O(N log N) | 정렬이 병목 |
| 공간 복잡도 | O(N) | 물건 배열 저장 |
주의사항
- 0-1 배낭에는 불가: 물건을 쪼갤 수 없으면 그리디로 안 됨
- 단위 가치 계산: 실수 연산 주의 (가치 / 무게)
- 정렬 기준: 반드시 단위 가치 내림차순
- 일부 담기: 마지막 물건은 비율 계산 필요
구현 팁
- 단위 가치 저장: 구조체나 클래스로 (무게, 가치, 비율) 저장
- 정렬:
Arrays.sort()또는Collections.sort()로 비율 기준 내림차순 - 실수 처리: 가치는
double로 계산
Last updated on