Example Suppose that n = 4, W = 16, and we have the following:
| 1 | $40 | 2 | $20 |
| 2 | $30 | 5 | $6 |
| 3 | $50 | 10 | $5 |
| 4 | $10 | 5 | $2 |
퇴각검색법
✅ 0-1 배낭문제 - 퇴각검색법 (Backtracking) 설명
📌 문제 예시
- 아이템 개수 n=4
- 배낭 용량 W=16
- 아이템 정보:
Item가치무게
| 1 | 40 | 2 |
| 2 | 30 | 5 |
| 3 | 50 | 10 |
| 4 | 10 | 5 |
📖 퇴각검색법이란?
- 가능한 모든 조합을 재귀적으로 탐색
- 탐색 도중 조건(무게 초과 등)을 만족하지 않으면 해당 경로를 즉시 중단 (가지치기)
- 최대 가치(maxValue) 를 저장하면서 갱신
✅ 트리 탐색 방식
- 트리의 각 레벨 = 아이템 인덱스
- 각 노드 = 해당 아이템을 선택할지/말지 결정
- 왼쪽 자식 = 선택함
- 오른쪽 자식 = 선택 안함
🌳 상태트리 예시 (그림과 연계)
(0,0) v=0, w=0
/ \
(1,1) v=40,w=2 (1,2) v=0,w=0
/ \ \
(2,1) v=70,w=7 (2,2) v=40,w=2 ...
/ \ / \
(3,1)... ... (3,3) v=90,w=12
→ 여기서 트리의 모든 경로를 따라가며, 조건을 만족하는 최대 가치를 찾습니다.
✅ Python 스타일 의사코드
# 초기값
maxValue = 0
def knapsack_backtrack(level, current_value, current_weight):
global maxValue
# 가지치기 1: 무게 초과 시 중단
if current_weight > W:
return
# 마지막 아이템까지 탐색했으면 최대값 갱신
if level == n:
maxValue = max(maxValue, current_value)
return
# 가지치기 2: bound 사용 (선택 사항)
# 아이템 포함하는 경우
knapsack_backtrack(
level + 1,
current_value + values[level],
current_weight + weights[level]
)
# 아이템 포함하지 않는 경우
knapsack_backtrack(
level + 1,
current_value,
current_weight
)
# 실행
values = [40, 30, 50, 10]
weights = [2, 5, 10, 5]
W = 16
n = 4
knapsack_backtrack(0, 0, 0)
print("최대 가치:", maxValue) # 출력: 90
✅ 탐색 흐름 예시
모든 가능한 조합을 살펴보면서:
선택 조합 (1~4)무게가치
| 1 + 2 + 3 | 17 | 120 ✖ 초과 |
| 1 + 2 + 4 | 12 | 80 |
| 1 + 3 | 12 | 90 ✅ |
| 2 + 3 | 15 | 80 |
| 1 + 2 | 7 | 70 |
| ... | ... | ... |
➡ 최대 가치 = 90 (물건 1 + 3)
✅ 퇴각검색법 vs 분기한정법
항목퇴각검색법분기한정법 (B&B)
| 전략 | 완전탐색 + 가지치기 | 상한값 계산 + 가지치기 |
| 탐색 순서 | DFS (재귀) | BFS or DFS |
| 가지치기 기준 | 무게 초과, 최대값보다 작음 | 무게 초과, bound(상한값) |
| 효율성 | 비교적 느림 (Bound 미사용 시) | 더 빠름 (Bound 적극 활용) |
🎯 핵심 요약
- 퇴각검색은 모든 경우의 수를 재귀적으로 탐색
- 무게 초과나 현재 가치가 의미 없을 경우 백트래킹(가지치기)
- 가장 단순한 구조이나, 시간복잡도는 O(2n)
너비우선 분기한정법
bound값 구하는 법
좋습니다! 업로드해주신 0-1 배낭문제 분기한정법 트리 이미지를 기준으로, bound (상한값) 이 어떻게 계산되는지 정확히 설명드릴게요.
✅ Bound(상한값)이란?
현재 노드에서 앞으로 선택할 수 있는 물건들을 최선의 방식으로 선택한다고 가정했을 때 얻을 수 있는 최대 가치입니다.
👉 즉, **그 노드에서 얻을 수 있는 가치의 최댓값(낙관적 예측)**을 의미합니다.
이를 통해 해당 노드가 확장 가치가 있는지(가치가 커질 가능성 있는지) 판단하고, 그렇지 않으면 가지치기(Pruning) 합니다.
📌 Bound 계산 방법 (Fractional Knapsack 기반)
- 현재 노드에서 이미 선택한 물건들의 가치(current value)와 무게(current weight)를 사용
- 남은 물건들을 가치/무게 비율 기준으로 정렬 (greedy하게 채움)
- 남은 배낭 용량만큼 가능한 물건들을 최대한 담고, 일부 물건은 **일부분(fractional)**만 담을 수도 있다고 가정하여 계산
📘 예시로 이해하기 (트리 그림 기준)
루트 노드:
- 선택한 물건 없음: 무게 = 0, 가치 = 0
- bound = 현재 가치 (0) + 앞으로 넣을 수 있는 물건 최대 가치 (Fractional Knapsack)
💡 주어진 데이터:
Item가치무게가치/무게 비율
| 1 | 40 | 2 | 20 |
| 2 | 30 | 5 | 6 |
| 3 | 50 | 10 | 5 |
| 4 | 10 | 5 | 2 |
✅ 루트 노드 Bound 계산 (0,0)
- 현재 가치 = 0, 남은 용량 = 16
- 가치/무게 비율 높은 순으로 넣기:
- Item 1: 무게 2 → 담음 (남은 용량: 14, 가치: 40)
- Item 2: 무게 5 → 담음 (남은 용량: 9, 가치: 70)
- Item 3: 무게 10 → 부분적으로 9만큼 담음 → 50 × (9/10) = 45
- 총 bound = 40 + 30 + 45 = 115
✅ 노드 (2,3) 예시 (value = 90, weight = 12)
- 남은 용량: 16 - 12 = 4
- 다음 남은 아이템: Item 4 (무게 5, 가치 10)
- 4/5 만큼 fractional하게 담기 → 10 × (4/5) = 8
- bound = 90 + 8 = 98
➡ 그림에서 (3,3) 노드가 바로 이 케이스입니다:
→ 표시된 bound: $98
✅ 노드 (3,2) 예시 (value = 70, weight = 7)
- 남은 용량: 9
- 남은 아이템: Item 3(무게 10, 가치 50), Item 4(무게 5, 가치 10)
- Item 3: 9/10만큼 → 50 × (9/10) = 45
- bound = 70 + 45 = 115
✅ 공식화된 Bound 계산식 (Python 스타일)
def calculate_bound(level, current_weight, current_value):
if current_weight > W:
return 0
result = current_value
total_weight = current_weight
i = level + 1
while i < n and total_weight + weights[i] <= W:
total_weight += weights[i]
result += values[i]
i += 1
if i < n:
remain = W - total_weight
result += values[i] / weights[i] * remain # fractional part
return result
✅ 정리
용어의미
| value | 현재까지 선택된 아이템의 총 가치 |
| bound | 현재까지 가치 + 남은 아이템을 greedy하게 채운다면 얻을 수 있는 최대 예측 가치 |
| 사용 이유 | 이 노드가 더 확장할 가치가 있는지 판단 (가지치기 조건) |