[Computation / Python] Knapsack Problems / Greedy Algorithm(최적화, Optimization)

 

ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/lecture-videos/lecture-1-introduction-and-optimization-problems/

Lecture 1: Introduction and Optimization Problems | Lecture Videos | Introduction to Computational Thinking and Data Science | E

※위 내용을 기반으로 제작하였습니다.

 

Knapsack Problem이란?

- 최적화의 한 방법임

- 우리가 가진 힘은 한정적임( 가방에 넣기에는 부피도 따져야겠지만 여기선 무게만 생각)

- 짊어질수 있는 이상의 무게론 담을 수 없음

- 어느것을 선택하고 어느것을 버릴것인지?

 

두가지버전

- 0/1 Knapsack problem

- Continuous or fractional kanpsac problem

 

왼쪽과 같이 갈아버린다면 Continuous(fractional) 오른쪽과 같이 가져감 또는 남김 이면 0/1

여기선 0/1 Knapsack Problem을 다룸. 왜냐하면 Continuous는 너무 쉬움(가장 가치있는것부터 순서대로 그냥 담으면 됨. 가루니까)

 

칼로리 섭취로 Knapsack 풀기 - 식으로 만들기

- 일정 칼로리이상 섭취하는 것

- 각 아이템은 <Value, weight> 짝으로 이루어짐. 즉, <가치, 무게>(상황에 따라 가치와 무게가 가르키는것이 다름)

- 배낭에는 무게 W이상의 물건을 넣을 수 없음

- 길이가 n인 벡터 L은 가용한 물건들을 가르킴(벡터를 리스트로 해석해도 무방할 듯)

- 길이가 n인 벡터 V는 물건을 가방에 담았는지 아닌지를 나타냄

- V[i] = 1 이면 L의 [i] 번째 아이템 즉, L[i]는 가방에 담긴것임

- 반대로 V[i] = 0 이면 L의 [i] 번째 아이템 즉, L[i]는 취하지 않음.

 

식으로 표현

V[i]*I[i].weight의 값(무게의합) w이하를 충족하면서 V[i]*I[i].value(가치의 합)을 최대화 하는 쌍을 찾는 것.

-> 위에 L이라 썼다가 I라 쓴것은 오타인듯

 

Brute Force Algorithm

- 무식한 알고리즘 정도로 보면 될듯

- 모든 경우의 수를 찾아서 그 중 무게 값은 w이하이면서 가치는 최대인 것을 찾는 것

- 하지만 대부분 실용적이지 못함

- 100개의 물건이 있다면 계산해야하는 양은 2^100 -> 1.2676506×10³⁰ 임

 

- 우리가 멍청한게 아님

- 0 /1 Knapsack 문제는 exponentail함

- 대체 알고리즘

 

Greedy Algorithm

Pseudo code로 표현하면 다음과 같음

while knapsack not full
	put “best” available item in knapsack

- 여기서 Best란?

- 가장 가치가 높은것?

- 가장 싼것?

- 무게당 가치가 가장 높은것?

 

예시

- 밥을 먹으려함

- 자신의 메뉴 선호도는 알고 있음. 예) 도넛을 사과보다 좋아한다

- 하지만 하루 칼로리 섭취량이 정해져있음. 예) 750 칼로리 이하로만 섭취

- 무엇을 먹을지 선택하는 것

 

메뉴

음식	와인	맥주	피자	햄버거	튀김	콜라	사과	도넛
가치	89	90	30	50	90	79	90	10
칼로리	123	154	258	354	365	150	95	195

 

프로그래밍

class Food(object):
	def __init__(self, n, v, w):
    	self.name = n
        self.value = v
        self.calories = w
        
       def getValue(self):
           return self.value
       def getCost(self):
           return self.calories
       def density(self):
           return self.getValue()/self.getCost()
       def __str__(self):
           return self.name + ": <" + str(self.value)\
                  + ', ' + str(self.calories) + '>'
                  
# 음식 메뉴 만들기

def buildMenu(names, values, calories):
	""" 세 리스트의 길이는 같음. 음식의 List를 반환"""
    menu = []
    for i in range(len(values)):
    	menu.append(Food(names[i],values[i],calories[i]))
    return menu
    
#Greedy알고리즘 구현

def greedy(items,maxCost, keyFunction):
	"""items와 maxCost >=0 이라고 가정. keyFunction은 무엇을 기준으로 sorting할지 결정함"""
    # keyFunction을 기준으로 sort. reverse = true이기때문에 내림차순(큰거 -> 작은거)
    # function을 받는다는것에 주목. 이후 lambda나오는 것과 연관됨
    itemsCopy = sorted(items, key = keyFunction, reverse = True)
    
    result = []
    #여기서 Cost는 칼로리로 보면 됨. Value는 keyFunction에 따라 다름
    totalValue, totalCost = 0.0, 0.0
    
    for i in range(len(itemsCopy)):
    	if(totalCost + itemsCopy[i].getCost()) <= maxCost:
            result.append(itemsCopy[i])
            totalCost += itemsCopy[i].getCost()
            totalValue += itemsCopy[i].getValue()

    return (result, totalValue)
    
def testGreedy(items,constraint, keyFunction):
    taken, val = greedy(items,contraint, keyFunction)
    print('Total value of items taken=', val)
    for item in taken:
        print('    ', item)
        
def testGreedys(foods,maxUnits):
    print('Use greedy by value to allocate',maxUnits,'calories')
    # value(여기선 만족도)가 큰 순서로
    testGreedy(foods, maxUnits, Food.getValue)
    print('\nUse greedy by value to allocate',maxUnits,'calories')
    #칼로리가 낮은것부터 순서대로
    testGreedy(foods, maxUnits, lambda x: 1/Food.getCost(x))
    print('\nUse greedy by value to allocate',maxUnits,'calories')
    #칼로리당 만족도가 높은 순서
    testGreedy(foods, maxUnits, Food.density)
    
#menu생성
names = ['wine', 'beer', 'pizza','burger', 'fries', 'cola', 'apple', 'donut', 'cake']
values = [89, 90, 95, 100, 90, 79, 50, 10]
calories = [123, 154, 258, 354, 365, 150, 95, 195]
foods = buildMenu(names, values, calories)
testGreedys(foods,750)

 

lambda란?

- def대신에 한줄로 쓰는 용도

- 위 코드에서 Food는 class name. 여기에 x를 넣음

- x의 타입은? Food임

 

실행결과

Use greedy by value to allocate 750 calories
Total value of items taken = 284.0
    burger: <100, 354>
    pizza: <95, 258>
    wine: <89, 123>

Use greedy by cost to allocate 750 calories
Total value of items taken = 318.0
    apple: <50, 95>
    wine: <89, 123>
    cola: <79, 150>
    beer: <90, 154>
    donut: <10, 195>

Use greedy by density to allocate 750 calories
Total value of items taken = 318.0
    wine: <89, 123>
    beer: <90, 154>
    cola: <79, 150>
    apple: <50, 95>
    donut: <10, 195>

- 750칼로리 이내에서 섭취

- 첫번째는 value가 높은 순서로 sort

- 두번째는 calory가 낮은 순서

- 세번째는 Density가 높은 순서. 즉, 칼로리당 만족도가 높은 순서