# 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[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?

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.

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

• You can always create a copy of the original dictionary and mutate the copy. – Nathan Davis Nov 16 '16 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][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.

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