Python Knapsack greedy

Question

Given a dictionary of cows and their weight:

cows = {'Betsy': 9, 'Oreo': 6, 'Herman': 7, 'Florence': 2, 'Maggie': 3, 'Moo Moo': 3, 'Milkshake': 2, 'Lola': 2, 'Millie': 5, 'Henrietta': 9}

I want to get a list of lists to move all cows, each nested list of cow's a total weight <= 10, hence to first two trips will have just Betsy and Henrietta:

The answer for GREEDY COW TRANSPORT:

[['Betsy'], ['Henrietta'], ['Herman', 'Maggie'], ['Oreo', 'Moo Moo'], ['Millie', 'Florence', 'Milkshake'], ['Lola']]

Here is my code that took too long in a net grader:

def greedy_cow_transport(cows,limit=10):
    train = []
    cart = [] 

# get tuples from dictionary key ordered by value high to low
    CowTupleList = sorted(cows.items(), key=lambda x: x[1], reverse = True)

# put cow names in list order high to low to loop over
    names = []
    for i in range(len(cows)):
        names.append(CowTupleList[i][0])
    train = []
    while sum(cows.values()) > 0:
        cart = []
        total = 0

        for cow in names:
            if cows[cow] != 0 and cows[cow] + total <=limit:
                cart.append(cow)
                total += cows[cow]
                cows[cow] = 0
        train.append(cart)
    return train

This took too much time for the online grader, so I failed. Can this be done in only a few lines?

Answer 1

You sort the cows, but you don't take advantage of the fact that they're sorted. Instead of iterating over the cows multiple times (which leads to \$\mathcal{O}(n^2)\$ time w.r.t. the number of cows), iterate over the sorted list once.

Unfortunately, I can't think of an easy way to do this using Python's built-in data structures. However, if we assume that CowTupleList is some list-like datastructure that has \$\mathcal{O}(\log{n})\$ or better performance for all operations (including del), then we can use binary search to find the largest cow that will fit in a cart's remaining capacity:

def greedy_cow_transport(cows,limit=10):
  # Sort cows from largest to smallest
  CowTupleList = sorted(cows.items(), key=lambda x: x[1], reverse = True)

  while CowTupleList:
    # Add first (largest) cow to a new cart
    name,weight = CowTupleList[0]
    cart = [name]
    remaining_capacity = limit - weight

    # Remove first cow from list
    del CowTupleList[0]

    # Find largest remaining cow that fits in remaining capacity (if any)
    idx = find_largest_fitting(CowTupleList, remaining_capacity)
    while idx is not None:
      # Add the cow at idx to the cart
      name,weight = CowTupleList[idx]
      cart.append(name)
      remaining_capacity -= weight

      # Remove cow at idx from list
      del CowTupleList[idx]

      # Find largest remaining cow that fits (if any)
      idx = find_largest_fitting(CowTupleList, remaining_capacity)

    # No more cows fit => yield the cart
    yield cart

Assuming find_largest_fitting is implemented as a binary search over CowTupleList (and an appropriate data structure is chosen for CowTupleList), this should take \$\mathcal{O}(n\log{n})\$ time. If linear search is used for find_largest_fitting and/or Python's build-in list type is used for CowTupleList (so that del operates in \$\mathcal{O}(n)\$), then this algorithm will operate in \$\mathcal{O}(n^2)\$ time.

Answer 2

This is the best I got so far:

def greedy_cow_transport(cows,limit=10):
    train = []
    while sum(cows.values()) > 0:
        cart = []
        total = 0
        for cow, value in sorted(cows.items(), key=lambda x: x[1], reverse = True):
            if cows[cow] != 0 and value + total <= limit:
                cart.append(cow)
                total += value
                cows[cow] = 0
        train.append(cart)
    return train

For the dictionary:

  cows = {'Betsy': 9,
 'Florence': 2,
 'Henrietta': 9,
 'Herman': 7,
 'Lola': 2,
 'Maggie': 3,
 'Milkshake': 2,
 'Millie': 5,
 'Moo Moo': 3,
 'Oreo': 6}

We get:

[['Betsy'],
 ['Henrietta'],
 ['Herman', 'Maggie'],
 ['Oreo', 'Moo Moo'],
 ['Millie', 'Milkshake', 'Lola'],
 ['Florence']] 

Although, I have mutated the original dictionary which we're not supposed to do.

Answer 3

I'll give it a shot too.

I wrote various iterations of the code for this problem and the one I'm the most happy about (and that is easy to read and understand) is the following where I use a while-loop but start the counter at one less than the length and decrease the value each time in order to not go through the list of cows more than once.

def greedy_cow_transport_third_iteration(cows, limit=10):
trips, available = [], limit
# Make a list of cows, sort by weight in ascending fashion (lightest first)
cows = sorted([(weight, name) for name, weight in cows.items()])
while cows:                     # Loop through available cows
    trips.append([cows[-1][1]]) # Allocate heaviest cow on a new trip
    available -= cows[-1][0]    # Adjust available weight accordingly
    cows.remove(cows[-1])       # Remove this cow from future loops
    i = len(cows) - 1           # Reset index
    while i >= 0:               # Loop back through all remaiing cows
        if available > 0 and cows[i][0] <= available:
            trips[-1].append(cows[i][1])  # Allocate this cow!
            available -= cows[i][0]       # adjust available weight
            cows.remove(cows[i])          # Remove it from future loops
        i -= 1                  # Avoid infinite loops
    available = limit           # Reset available weight for next trip
return trips                    # Returns solution

I hope that helps somehow.