MITx - 6.00.2x 笔记(Unit1 Lecture 2 Decision Trees and Dynamic Programming)

Lecture 2 Decision Trees and Dynamic Programming

Brute Force Algorithms

暴力算法，穷举法

Decision Tree

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
        return 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(items)):
        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)

def maxVal(toConsider, avail):
    """Assumes toConsider a list of items, avail a weight
        Return a tuple of the total value of a solution to the
        0/1 knapsack problem and the items of that solution"""

    if toConsider == [] or avail == 0:
        result = (0.0, ())
    elif toConsider[0].getCost() > avail:
        # Explore right branch only
        result = maxVal(toConsider[1: ], avail)
    else:
        nextItem = toConsider[0]
        # Explore left branch
        withVal, withToTake = maxVal(toConsider[1: ],
                                                          avail - nextItem.getCost())
        withVal += nextItem.getValue()
        # Explore right branch
        withoutVal, withoutToTake = maxVal(toConsider[1: ], avail)
        # Choose better branch
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem, ))
        else:
            result = (withoutVal, withoutToTake)
    return result

def testMaxVal(foods, maxUnits, printItems = True):
    print('Use search tree to allocate', maxUnits, ' calories')
    val, taken = maxVal(foods, maxUnits)
    print('Total value of items taken =', val)
    if printItems:
        for item in taken:
            print('    ', item)

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)
print(' ')
testMaxVal(foods, 750)

# Out:
    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>

    Use search tree to allocate 750  calories
    Total value of items taken = 353.0
         cola: <79, 150>
         pizza: <95, 258>
         beer: <90, 154>
         wine: <89, 123>

背包问题示例

# generate all combinations of N items
def powerSet(items):
    N = len(items)
    # enumerate the 2**N possible combinations
    for i in range(2**N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            # ">>" is one bit right move in binary, equals divde 2**j
            # check jth digit of integer i, if 1 take it
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

共有N个物品，决定是否放入背包中，每个物品放或者不放，共有2N$2^N$种可能。
要求列出所有放入的组合，所以只考虑(i >> j) % 2 == 1的情况，>>为按位运算符。

习题：
假设将N个物品放入两个背包中，遍历各种组合。

def yieldAllCombos(items):
    """
        Generates all combinations of N items into two bags, whereby each 
        item is in one or zero bags.

        Yields a tuple, (bag1, bag2), where each bag is represented as a list 
        of which item(s) are in each bag.
    """
    # Your code here
    N = len(items)
    for i in range(3**N):
        bag_1 = []
        bag_2 = []
        for j in range(N):
            if (i // 3**j) % 3 == 1:
                bag_1.append(items[j])
            elif (i // 3**j) % 3 == 2:
                bag_2.append(items[j])
        yield (bag_1, bag_2)

Recursive Fibonacci

直接用递归计算斐波那契数列效率很低，算到第十几个数的就至少要好几秒，用这种方法算第120个数简直不可能。

复习一下6.00 1x中讲过的优化方法，用字典存储已经算过的fib数，可以直接调用从而避免重复计算：

def fastFib(n, memo = {}):
    """Assumes n is an int >= 0, memo used only by recursive calls
        Return Fibonacci of n"""

    if n ==0 or n == 1:
        return 1
    try:
        return memo[n]
    except KeyError:
        result = fastFib(n-1, memo) + fastFib(n-2, memo)
        memo[n] = result
        return result

fastFib(120)不到1秒就出结果。

Dynamic Programming（动态规划）

小结

• • Lecture 2 Decision Trees and Dynamic Programming

参考：
递归、分治策略、动态规划以及贪心算法之间的关系