Mar-30-2019, 11:21 PM
I modified the code by adding a brute force algorithm
# Brute Force Algorithms 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): menu = [] for i in range(len(values)): menu.append(Food(names[i], values[i], calories[i])) return menu def greedy(items, maxCost, keyFunction): 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) def maxVal(toConsider, avail): if toConsider == [] or avail == 0: result = (0, ()) elif toConsider[0].getCost() > avail: result = maxVal(toConsider[1:], avail) else: nextItem = toConsider[0] withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost()) withVal += nextItem.getValue() withoutVal, withoutToTake = maxVal(toConsider[1:], avail) if withVal > withoutVal: result = (withVal, withToTake + (nextItem)) else: result = (withoutVal, withoutToTake) return result def testMaxVal(foods, maxUnits, printItems=True): print("Our 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, 1000) print("") testMaxVal(foods, 750)but an error that I don't understand occures
Error:Traceback (most recent call last):
File "C:\Python36\kodovi\6.00.2x\brute.py", line 92, in <module>
testMaxVal(foods, 750)
File "C:\Python36\kodovi\6.00.2x\brute.py", line 79, in testMaxVal
val, taken = maxVal(foods, maxUnits)
File "C:\Python36\kodovi\6.00.2x\brute.py", line 67, in maxVal
withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost())
File "C:\Python36\kodovi\6.00.2x\brute.py", line 67, in maxVal
withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost())
File "C:\Python36\kodovi\6.00.2x\brute.py", line 67, in maxVal
withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost())
File "C:\Python36\kodovi\6.00.2x\brute.py", line 64, in maxVal
result = maxVal(toConsider[1:], avail)
File "C:\Python36\kodovi\6.00.2x\brute.py", line 64, in maxVal
result = maxVal(toConsider[1:], avail)
File "C:\Python36\kodovi\6.00.2x\brute.py", line 67, in maxVal
withVal, withToTake = maxVal(toConsider[1:], avail - nextItem.getCost())
File "C:\Python36\kodovi\6.00.2x\brute.py", line 64, in maxVal
result = maxVal(toConsider[1:], avail)
File "C:\Python36\kodovi\6.00.2x\brute.py", line 64, in maxVal
result = maxVal(toConsider[1:], avail)
File "C:\Python36\kodovi\6.00.2x\brute.py", line 70, in maxVal
if withVal > withoutVal:
UnboundLocalError: local variable 'withVal' referenced before assignment