그리디 알고리즘

이론_전공/알고리즘

그리디 알고리즘

오뀨기 2020. 11. 9. 21:43

★ 그리디 알고리즘

- 최적화 문제를 해결하는 알고리즘

- 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림

☆ 종류

1. 동전 거스름돈 문제

2. 최소 신장 트리

3. Dijkstra(다익스트라) 최단 경로

4. 부분 배낭 문제

5. 집합 커버 문제

6. 작업 스케줄링 문제

★ 배낭 문제

- 최대의 가치를 갖도록 배낭에 넣을 물건들은 정하는 문제

(-> n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 경우)

☆ 부분 배낭 (Fractional Knapsack) 문제

- 물건을 부분적으로 담는 것을 허용

- 그리디 알고리즘으로 해결

☆ 0-1 배낭 문제 (0/1 배낭 문제)

- 부분 배낭 문제의 원형으로 물건을 통째로 배낭에 넣어야 함

- 동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결

★ 부분 배낭 문제

- 물건을 부분적으로 배낭에 담을 수 있으므로, 최적해를 위해서 ‘욕심을 내어’ 단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣게 됨

- 만일 그 다음으로 값나가는 물건을 ‘통째로’ 배낭에 넣을 수 없게 되면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 넣음

★ 부분 배낭 문제 그리디 알고리즘

입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C

출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건 가치의 합 v

각 물건에 대해 단위 무게 당 가치를 계산한다.
물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬하고, 정렬된 물건 리스트를 S라고 하자.
L=∅, w=0, v=0  // L은 배낭에 담을 물건 리스트, w는 배낭에 담긴 물건들의 무게의 합, v는 배낭에 담긴 물건들의 가치의 합
S에서 단위 무게 당 가치가 가장 큰 물건 x를 가져온다.
while ( (w+x의 무게) ≤ C ) { 
     x를 L에 추가시킨다.
     w = w+x의 무게
     v = v+x의 가치
     x를 S에서 제거한다.
	S에서 단위 무게 당 가치가 가장 큰 물건 x를 가져온다. }
if ((C-w) > 0) { // 배낭에 물건을 부분적으로 담을 여유가 있으면 
	물건 x를 (C-w)만큼만 L에 추가한다. 
 	v = v +(C-w)만큼의 x의 가치 }
return L, v