Python Forum
Optimization problem ( food menu )
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Optimization problem ( food menu )
#1
# -*- 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?
Output:
burger: <100, 354> pizza: <95, 258> wine: <89, 123>
Reply
#2
https://docs.python.org/3.3/reference/da...ct.__str__
Python docs Wrote:object.__str__(self)
Called by str(object) and the built-in functions format() and print() to compute the “informal” or nicely printable string representation of an object. The return value must be a string object.

This method differs from object.__repr__() in that there is no expectation that __str__() return a valid Python expression: a more convenient or concise representation can be used.

The default implementation defined by the built-in type object calls object.__repr__().

Calling print on the Food object will print the returned string from the __str__ method
Reply
#3
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
Reply
#4
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.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  [PROBLEM] Removing IDLE from context menu WebSpider 1 426 Sep-28-2023, 03:35 PM
Last Post: deanhystad
  optimization problem for dataframe manipulation fimmu 0 1,436 Aug-31-2020, 06:02 PM
Last Post: fimmu
  Problem in solving optimization problem Ruchika 0 1,519 Jul-27-2020, 05:28 AM
Last Post: Ruchika
  Problem with user defined main menu function stefzeer 3 2,341 Mar-27-2020, 06:12 AM
Last Post: buran
  Help on a program to help with distributing food to the needy teenspirit 39 22,945 Apr-12-2017, 10:44 PM
Last Post: sparkz_alot

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020