거스름돈 문제

• 최소의 동전 개수로 거스름돈을 거슬러주는 문제

1. 가장 효율적인 방법

• 남은 액수를 초과하지 않는 조건에서 '욕심내어' 가장 큰 금액을 갖는 동전을 취하는 것

CoinChange()
- 입력: 거스름돈 액수W
- 출력: 거스름돈 액수에 대한 최소 동전 수
change=W, n500 = n100= n50= n10= n1=0
while(change>=500) change -= 500 AND n500 += 1
while(change>=100) change -= 100 AND n100 += 1
while(change>=50) change -= 50 AND n50 += 1
while(change>=10) change -= 10 AND n10 += 1
while(change>=1) change -= 1 AND n1 += 1
return (n500, n100. n50. n10, n1)

2. CoinChange 알고리즘

• 그리디 알고리즘의 근시안적인 특성
  • CoinChange 알고리즘은 남아있는 거스름돈인 change에 대해 가장 높은 가격을 갖는 거스름돈을 제공
  • 가장 높은 가격의 코인을 처리할 때 그 보다 낮은 코인은 전혀 고려하지 않음
• 문제점
  • 한국 동전의 단위에서는 사용될 수 있지만 160원 같이 단위가 달라진다면 문제가 발생 가능
    • 200원 거스름돈에 대한 CoinChange 알고리즘의 결과
      
    • 최적해
      
  • 결론적으로, CoinChange 알고리즘의 결과가 항상 최적의 해결책임을 보장할 수 없음

---

배낭 문제

• n개의 물건이 각각 1개씩 존재
• 각 물건은 무게와 가치를 가지고 있음
• 배낭이 한정된 무게의 물건들을 담을 수 있음
• 최대의 가치를 가지도록 재낭에 넣을 물건을 정함
• 부분 배낭 문제임

1. 풀이 방법

FractionalKnapsack()
- 입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C
- 출력: 배낭에 담은 물건 리스트 L과 배낭 속의 물건 가치의 합 V
1. 각 물건에 대해 단위 무게 당 가치를 계산
2. 물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정령하고, 정렬된 물건 리스트를 S라 함
3. L=∅; w=0; v=0; 
4. S에서 단위 무게 당 가치가 가장 큰 물건 x를 가져옴\
5. While w+(x의 무게) <= C
6.   x를 L에 추가
7.   w = w+(x의 무게)
8.   v = v+(x의 가치)
9.   x를 S에서 제거
10.  S에서 단위 무게 당 가치가 가장 큰 물건 x를 가져옴
11. if(C-w>0)
12.   물건 x를 (C-w)만큼만 L에 추가
13.   v = v+(C-w) 만큼의 x의 가치
14. return L,v

2. 알고리즘의 시간복잡도

• n개의 물건 각각의 단위 무게 당 가치를 계산하는 데에 O(n) 시간 소요
• 물건의 단위 무게 당 가치에 대해 정렬하기 위해 O(nlogn) 시간 소요
• while-루프 수행은 n번을 넘지 않으며, 루프 내부의 수행은 O(1) 시간 소요
• 가치와 무게를 더하는 과정, O(1) 시간 소요
• 알고리즘의 총 시간복잡도 O(n)+O(nlogn)+(n*O(1))+O(1) = O(nlogn)