-
Notifications
You must be signed in to change notification settings - Fork 0
/
buy.py
99 lines (84 loc) · 3.57 KB
/
buy.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
""" Determine what items the user should buy contained by the amount of money they have. """
def selectBuys(budget: int, yearlyWantsPrices: list, yearlyWantsValues: list,
oneTimeWantsPrices: list, oneTimeWantsValues: list) -> (list, list, int, float):
""" Selects the optimal items to buy to maximize the happiness value.
Parameters
----------
budget : int
- maximum amount of money that can be spent
yearlyWantsPrices : list
yearlyWantsValues : list
- prices or happiness values for all the yearly wanted items
- examples of yearly wants are netflix subscriptions or amusement park passes
oneTimeWantsPrices : list
oneTimeWantsValues : list
- prices or happiness values for all wanted items that are purchased once
- examples of one time wants are laptops or the latest fashionable clothing
Returns
-------
* list -> yearly wants that should be bought
* list -> one time purchases that should be bought
* int -> happiness attained for all items bought
* float -> total price of all purchases
"""
# Best items to buy (knapsack algorithm)
cumulativePrices = yearlyWantsPrices + oneTimeWantsPrices
cumulativeValues = yearlyWantsValues + oneTimeWantsValues
for i in range(len(cumulativePrices)): # knapsack requires int
cumulativePrices[i] = int(cumulativePrices[i] * 100)
cumulativeValues[i] = int(cumulativeValues[i] * 100)
allPurchases, happiness = knapsack(
cumulativePrices, cumulativeValues, int(budget * 100))
# Which yearly vs. one time items were bought
yearlyPurchases = []
oneTimePurchases = []
mwCount = len(yearlyWantsPrices)
for itemBought in allPurchases:
# the item is within the range of yearly wants
if itemBought < mwCount:
yearlyPurchases.append(itemBought)
else: # item is a one time purchase
oneTimePurchases.append(itemBought - mwCount)
# Total price of all purchases
totalPrice = 0
for item in yearlyPurchases:
totalPrice += yearlyWantsPrices[item]
for item in oneTimePurchases:
totalPrice += oneTimeWantsPrices[item]
# return all yearly and one time purchases made,
# happy it will make the user, and how much it costs
return yearlyPurchases, oneTimePurchases, happiness, totalPrice
def knapsack(prices: list, values: list, budget: int) -> list:
""" Knapsack algorithms that backtracks to determine what items were brought
Parameters
----------
prices : list
- prices of all the items that can be "packed"
values : list
- happiness value attained from each item
budget : int
- maximum amount of money that can be spent
Returns
-------
* list -> items to buy
"""
# run the knapsack algorithm
knapsackMat = [[]]
for i in range(budget + 1):
knapsackMat[0].append(0)
for i in range(len(prices)):
knapsackMat.append([])
for j in range(budget + 1):
usingItemI = knapsackMat[i][j]
if j >= prices[i]:
usingItemI = knapsackMat[i][j - prices[i]] + values[i]
knapsackMat[i + 1].append(max(knapsackMat[i][j], usingItemI))
# figure out what items to include
including = []
currSpent = budget
for i in range(len(prices), 0, -1):
if knapsackMat[i][currSpent] != knapsackMat[i - 1][currSpent]:
currSpent -= prices[i - 1]
including.append(i - 1)
# return the items the include, max happiness
return including, knapsackMat[len(prices)][budget]