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.

• Andrew Church: BINGO! Thank you nathan, yeild statements, another way...
• Andrew Church: BUT WAIT, you MIGHT fit a very light cow further down the list. Dont you have to check the entire list each time? That would be VERY greedy otherwise. Greedy is what we did (without knowing it) when choosing the words from a hand in scrabble, ONLY you didn't have to delete a word once it was chosen.... grrrrrrrr
• Nathan Davis: Ah yes, you are right, of course. Don't know what I was thinking.
• Nathan Davis: Although about checking the entire list ... you are only interested in the portion of the list that has cows that are no heaver than the remaining capacity. So I suppose you could use a binary search to find the largest cow that fits?
• Andrew Church: Thanks so much Nat, YOURS was the major DUH!! moment with the <name, weight in tuples> ...

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.

• Nathan Davis: You can always create a copy of the original dictionary and mutate the copy.

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.

• Mast: Each and every answer on Code Review should contain an insightful comment about the code provided. This is an alternative implementation without reviewing the code provided. Either provide a review or your answer isn't up to par.
• Mast: Afar from that, welcome to Code Review!
• Carlo Rizzante: Ok, sorry about that, and thanks :) I can also delete my reply altogether if that's for the better.