key words

#Computer Model #Optimization Model #Greedy algorithms

knapsack Problem(냅색 문제)

constraint -> enough to put in a knapsack
: 도둑이 가장 값 비싼 물건을 훔쳐야 하는 optimization problem

Two variants

0/1 knapsack problem vs Continuous or fractional knapsack problem

0/1 knapsack problem : 현재의 결정이 다음 결정에 영향을 끼침
Continuous or fractional knapsack problem : 연속 문제는 아주 쉬운 문제. Greedy algorithm으로 풀 수 있음.

0/1 knapsack problem

• Each item is represented by a pair, <value, weight>.
• The knapsack can accomodate items with a total weight of no more than w.
• A vector, L , of length n, represented the set of available items.
  (Each element of the vector is an item.)
• A vector, V , of length n, is used to indicate whether or not items are taken.
  ex) V[i]=1 이면, i번 째 물건은 가져간 것. V[i]=0이면, i번 째 물건은 가져가지 않은 것.
  

이를 수학적으로 표현하면,

Find a V that maximizes
$\sum_{i=0}^{n-1}$ V[i]I[i].value
subject to the constraint that
$\sum_{i=0}^{n-1}$ V[i]I[i].weight <= w

Solution) Brute Force Algorithm(완전 탐색)

1. Enumerate all possible combinations of items.(멱집합 구하기)
2. Remove all of the combinations whose total units exceeds the allowed weight.
3. From the remaining combinations choose anyone whose value is the largest.

-> often Not Practical!!!
이는 모든 경우의 수를 고려하는 알고리즘. 최적의 해를 구할 수 있지만, 벡터의 길이가 길어질 경우, 매우 오래걸리고 복잡함. 이 방법만큼 최적의 해를 찾는 좋은 algorithm은 없지만, 꽤 좋은 algorithm은 존재.

Another Solution is the "Flexible Greedy"

실습 코드

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):
    """names, values, calories lists of same length.
       name a list of strings
       values and calories lists of numbers
       returns list of Foods"""
    menu = []
    for i in range(len(values)):
        menu.append(Food(names[i], values[i],
                          calories[i]))
    return menu

def greedy(items, maxCost, keyFunction):
    """Assumes items a list, maxCost >= 0,
         keyFunction maps elements of items to numbers"""
    itemsCopy = sorted(items, key = keyFunction,
                       reverse = True)
    result = []
    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, constraint, 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')
    testGreedy(foods, maxUnits, Food.getValue)
    print('\nUse greedy by cost to allocate', maxUnits,
          'calories')
    testGreedy(foods, maxUnits,
               lambda x: 1/Food.getCost(x))
    print('\nUse greedy by density to allocate', maxUnits,
          'calories')
    testGreedy(foods, maxUnits, Food.density)


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, 1000)

코드 내부에서 sorted를 사용 -> python에서는 팀 정렬을 사용하는데, 이 정렬의 가장 나쁜 시간 복잡도는 n log n (여기서의 n은 물건의 개수를 뜻함.)

최종 시간복잡도 또한 n log n이기 때문에, 꽤 효율적인 알고리즘.

+) python 문법 설명
파이썬 람다(lambda) 표현식

• 익명(=이름이 없는)의 함수를 만들 때 사용
• (lambda 식별자 배열 : 원하는 식)
• 이 파라미터들로 표현된 식을 계산하고 결과를 반환하는 함수를 만듬
• def를 쓰는 대신에 인라인 함수로 정의