Optimization problem ( food menu ) - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: General Coding Help (https://python-forum.io/forum-8.html) +--- Thread: Optimization problem ( food menu ) (/thread-17111.html) |
Optimization problem ( food menu ) - Truman - Mar-28-2019 # -*- coding: utf-8 -*- """ Created on Thu Mar 28 00:56:50 2019 @author: TrumanB """ 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) 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)The script works fine but there is one thing that I don't understand. Why this piece of code: for item in taken: print(" ", item)prints line 25 (def __str__(self)) with name, value and calories? What is the connection with class Food?
RE: Optimization problem ( food menu ) - Yoriz - Mar-28-2019 https://docs.python.org/3.3/reference/datamodel.html?highlight=__str__#object.__str__ Python docs Wrote:object.__str__(self) Calling print on the Food object will print the returned string from the __str__ method
RE: Optimization problem ( food menu ) - Truman - Mar-30-2019 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
RE: Optimization problem ( food menu ) - Truman - Apr-01-2019 for those who may be interested in the answer this block of code has to be one level in ( below else ): if withVal > withoutVal: result = (withVal, withToTake + (nextItem,)) else: result = (withoutVal, withoutToTake)I also had to add comma to avoid some error that I don't understand. |