Revisions to Python Knapsack greedy

Math markup.

Source Link

edited Nov 16, 2016 at 18:32

11.4k
26
65

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 O(n^2)\$\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 O(log(n))\$\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 O(n*log(n))\$\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 O(n)\$\mathcal{O}(n)\$), then this algorithm will operate in O(n^2)\$\mathcal{O}(n^2)\$ time.

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 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 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 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 O(n)), then this algorithm will operate in O(n^2) time.

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.

Fix flawed logic preventing smaller cows from being fit into a cart

Source Link

edited Nov 16, 2016 at 17:52

Nathan Davis

905
4
14

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 O(n^2) time w.r.t. the number of cows), iterate over the sorted list once.

Here's howUnfortunately, I wouldcan't think of an easy way to do it,this using Python's built-in data structures. However, if we assume that CowTupleList is some list-like datastructure that has 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 generator functioncart's remaining capacity:

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

  forwhile CowTupleList:
    # Add first (largest) cow to a new cart
    name,weight in= CowTupleList:CowTupleList[0]
    ifcart weight= +[name]
 cart_weight >  remaining_capacity = limit:
 - weight

    # currentRemove first cow isfrom toolist
 big to fit indel currentCowTupleList[0]

 cart => send it# offFind largest remaining cow that fits in remaining capacity (yieldif itany)
    idx = yieldfind_largest_fitting(CowTupleList, cartremaining_capacity)
    while idx is not None:
      # resetAdd accumulators
the cow at idx to the cart
      name,weight = []CowTupleList[idx]
      cart_weightcart.append(name)
      remaining_capacity -= 0weight

    # Add current# Remove cow toat cartidx from list
    cart.append  del CowTupleList[idx]

      # Find largest remaining cow that fits (nameif any)
    cart_weight += weightidx = find_largest_fitting(CowTupleList, remaining_capacity)

    # SendNo themore lastcows cartfit off=> yield the cart
    yield cart

Ignoring the sorting operationAssuming find_largest_fitting is implemented as a binary search over CowTupleList (and an appropriate data structure is chosen for CowTupleList), this should take 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 O(n)), then this algorithm will operate in O(n^2) time.

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 O(n^2) time w.r.t. the number of cows), iterate over the sorted list once.

Here's how I would do it, using a generator function:

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

  CowTupleList = sorted(cows.items(), key=lambda x: x[1], reverse = True)
  for name,weight in CowTupleList:
    if weight + cart_weight > limit:
      # current cow is too big to fit in current cart => send it off (yield it)
      yield cart

      # reset accumulators
      cart = []
      cart_weight = 0

    # Add current cow to cart
    cart.append(name)
    cart_weight += weight

  # Send the last cart off
  yield cart

Ignoring the sorting operation, this operates in O(n) time.

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 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 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 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 O(n)), then this algorithm will operate in O(n^2) time.

Source Link

answered Nov 16, 2016 at 0:50

Nathan Davis

905
4
14

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 O(n^2) time w.r.t. the number of cows), iterate over the sorted list once.

Here's how I would do it, using a generator function:

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

  CowTupleList = sorted(cows.items(), key=lambda x: x[1], reverse = True)
  for name,weight in CowTupleList:
    if weight + cart_weight > limit:
      # current cow is too big to fit in current cart => send it off (yield it)
      yield cart

      # reset accumulators
      cart = []
      cart_weight = 0

    # Add current cow to cart
    cart.append(name)
    cart_weight += weight

  # Send the last cart off
  yield cart

Ignoring the sorting operation, this operates in O(n) time.

Stack Exchange Network

Return to Answer