Optimization problem ( food menu )

[Truman]

# -*- 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>

[Yoriz]

https://docs.python.org/3.3/reference/da...ct.__str__

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

[Truman]

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

[Truman]

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.