Greedy Algorithms: One Function, Any Definition of Best

How does passing a key function let one greedy algorithm handle every definition of "best" in O(n log n) time?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Value per calorie: the density method

The Food class below is missing the body of density, which should return the food's value per unit of cost. Write it using the two getter methods (not the attributes directly), so it keeps working for any kind of cost. Complete density in the Food class.

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 ...  # value per unit of cost, via the getters

    def __str__(self):
        return f'{self.name}: <{self.value}, {self.calories}>'

wine = Food('wine', 89, 123)

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 ...  # value per unit of cost, via the getters

    def __str__(self):
        return f'{self.name}: <{self.value}, {self.calories}>'

wine = Food('wine', 89, 123)

Python runs in your browser

⌘/Ctrl + Enter runs

wine.density() returns a float

wine's density is value over cost

works for another food

asks the getters, not the attributes

←Previous Brute-Force Knapsack and the Exponential Power Set Next Lambda Keys and Why Greedy Can Miss the Optimum →