/
Unit 1 - Lecture 2 - 10 brute force dynamic programming.py
135 lines (117 loc) · 4.04 KB
/
Unit 1 - Lecture 2 - 10 brute force dynamic programming.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
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 are lists of same length.
name - a list of strings
value & calories - lists of nums
return: list of Foods'''
menu = []
for i in range(len(values)):
menu.append(Food(names[i], values[i], calories[i]))
return menu
# brute force
def maxVal(toConsider, avail):
'''toConsider: a list of items
avail: weight available
return: a tuple of total value of a solution to knapsack problem and the list of chosen item'''
# number of calls
global numSlowCalls
numSlowCalls += 1
# nothing left or no space left
if toConsider == [] or avail == 0:
result = (0, ())
# next item exceeds the space left
elif toConsider[0].getCost() > avail:
result = maxVal(toConsider[1:], avail)
# not exceeds, compare take or not take
else:
# take
nextItem = toConsider[0]
withVal, withToTake = maxVal(
toConsider[1:], avail - nextItem.getCost())
withVal += nextItem.getValue()
# not take
withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
# compare
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
return result
# dynamic programming with number
# brute force
def fastmaxVal(toConsider, avail, memo = {}):
'''toConsider: a list of items
avail: weight available
return: a tuple of total value of a solution to knapsack problem and the list of chosen item'''
# counting
global numFastCalls
numFastCalls += 1
# check dict first
if (len(toConsider), avail) in memo:
result = memo[(len(toConsider), avail)]
# nothing left or no space left
elif toConsider == [] or avail == 0:
result = (0, ())
# next item exceeds the space left
elif toConsider[0].getCost() > avail:
result = fastmaxVal(toConsider[1:], avail, memo)
# not exceeds, compare take or not take
else:
# take
nextItem = toConsider[0]
withVal, withToTake = fastmaxVal(
toConsider[1:], avail - nextItem.getCost(), memo)
withVal += nextItem.getValue()
# not take
withoutVal, withoutToTake = fastmaxVal(toConsider[1:], avail, memo)
# compare
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
# update memo
memo[(len(toConsider), avail)] = result
return result
# test with different funcs
def testMaxVal(foods, maxUnits, algorithm, printItems = True):
print("Menu contains", len(foods), "items")
print('Search tree', maxUnits, 'calories')
val, taken = algorithm(foods, maxUnits)
print('Total value of item taken =', val)
if printItems:
for item in taken:
print(" -", item)
# build large menu
import random
def buildLargeMenu(numItems, maxVal, maxCost):
items = []
for i in range(numItems):
items.append(Food(str(i), random.randint(1, maxVal), random.randint(1, maxCost)))
return items
# dynamic programming test
# slow version
numSlowCalls = 0
numFastCalls = 0
for numItems in range(35):
items = buildLargeMenu(numItems, 90, 250)
testMaxVal(items, 750, maxVal, False)
testMaxVal(items, 750, fastmaxVal, False)
print("slow calls =", numSlowCalls, "fast calls =", numFastCalls, "\n")
# # fast version
# for numItems in range(0, 5000, 20):
# numCalls = 0
# items = buildLargeMenu(numItems, 90, 250)
# testMaxVal(items, 750, fastmaxVal, False)
# print("number of calls =", numCalls)