/
Unit 1 - Lecture 1 - 03 optimal value.py
75 lines (56 loc) · 2.07 KB
/
Unit 1 - Lecture 1 - 03 optimal value.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
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
def greedy(items, maxCost, keyFunction):
'''Assums items a list, maxCost >= 0,
keyFunction maps elements of items to numbers'''
itemsCopy = sorted(items, key=keyFunction, reverse=True)
result = []
totalValue, totalCost = 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)
# test
def testGreedy(items, constraint, keyFunction):
taken, val = greedy(items, constraint, keyFunction)
print('Total value of item take =', val)
for item in taken:
print(' -', item)
# batch test
def testGreedys(foods, maxUnits):
print('Greedy by value', maxUnits, 'calories')
testGreedy(foods, maxUnits, Food.getValue)
print("\nGreedy by cost", maxUnits, 'calories')
testGreedy(foods, maxUnits, lambda x: 1 / Food.getCost(x))
print('\nGreedy by density', maxUnits, 'calories')
testGreedy(foods, maxUnits, Food.density)
# data
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)
testGreedys(foods, 1000)