# Python Knapsack greedy

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, 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])
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?

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, reverse = True)

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

# Remove first cow from list
del CowTupleList

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

• BINGO! Thank you nathan, yeild statements, another way... Nov 16, 2016 at 1:10
• 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 Nov 16, 2016 at 1:22
• Ah yes, you are right, of course. Don't know what I was thinking. Nov 16, 2016 at 2:38
• 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? Nov 16, 2016 at 2:44
• Thanks so much Nat, YOURS was the major DUH!! moment with the <name, weight in tuples> ... Nov 16, 2016 at 10:11

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, 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.

• You can always create a copy of the original dictionary and mutate the copy. Nov 16, 2016 at 3:24

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]]) # Allocate heaviest cow on a new trip
available -= cows[-1]    # 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] <= available:
trips[-1].append(cows[i])  # Allocate this cow!
available -= cows[i]       # 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.

• 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
Dec 27, 2017 at 14:55
• Afar from that, welcome to Code Review!
– Mast
Dec 27, 2017 at 14:56
• Ok, sorry about that, and thanks :) I can also delete my reply altogether if that's for the better. Dec 28, 2017 at 13:03