- 최적의 해에 가까운 값을 구하는 방법이나, 최적의 해라고 확신할 수는 없음 (근사치 추정) => 한계
- 매 순간 최적이라고 생각되는 경우 한 가지를 선택하는 방법
- 동적 계획법의 computation complexity를 극복하기 위해 나온 기법
1. 동전 문제
- 최종 지불 가격 = 4720
- 1원, 50원, 100원, 500원 동전을 가지고 최소한의 동전 개수로 지불하는 방법
=> 가장 큰 동전으로 먼저 지불하고, 남은 금액이 해당 동전보다 적은 경우 다음 동전으로 지불하는 방식
=> 그러면 일단 동전의 크기가 큰 순서대로 sorting
def paiedCoin(coins, pay):
result = list()
count = 0
coins.sort(reverse = True) # 큰 순서대로 sorting
for c in coins:
num = pay//c
count += num
pay -= num*c
result.append([c,num])
return count, result
coins = [1,50,100,500]
pay = 4720
paiedCoin(coins, pay)
2. 부분 배낭 문제 (Fractional Knapsack Problem)
** 물건을 쪼개서 넣을 수 없는 배낭 문제는 "0/1 Knapsack problem"이라고 함
- 무게 제한이 k인 배낭에 최대 가치를 가지도록 문제를 넣는 문제
- 각 물건) 무게(w) & 가치(v)
- 최대의 가치를 담으려면, v/w 가 큰 순서대로 sorting
def FracKnapsack(items, size):
fin_value = 0
result = dict()
items.sort(reverse = True ,key = lambda k : k[2]/k[1]) #무게 대비 가치가 높은 순 서대로 정렬
for item in items:
if size - item[1] >= 0:
size -= item[1]
fin_value += item[2]
result[item[0]] = 1 # 1 => 100% 다 넣었다는 의미
else:
fin_value += (item[2]/item[1])*size
result[item[0]] = size/item[1] # size/item[1] % 만큼 넣었음
break
# else문으로 들어왔다는 것은, 이 계산 후에 더 이상 넣을 공간이 없다는 것
# 다음 for문 진행을 하지 않아도 되므로 break
return fin_value, result
'Study > 자료구조 | 알고리즘' 카테고리의 다른 글
4. 자료구조 - 트리 (0) | 2020.08.09 |
---|---|
3. 자료구조 - 해쉬 테이블 (0) | 2020.07.29 |
2. 자료구조 - 링크드 리스트 (0) | 2020.07.25 |
1. 자료구조 - 배열, 큐, 스택 (0) | 2020.07.13 |
0. 자료구조 / 알고리즘 (0) | 2020.07.11 |