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.

StackExchange Code Review Q#147149, answer score: 3