Fill order from smaller packages?

  • A+

The input is an integer that specifies the amount to be ordered. There are predefined package sizes that have to be used to create that order.


Packs 3 for $5 5 for $9 9 for $16 

for an input order 13 the output should be:

2x5 + 1x3 

So far I've the following approach:

remaining_order = 13 package_numbers = [9,5,3] required_packages = []  while remaining_order > 0:     found = False     for pack_num in package_numbers:         if pack_num <= remaining_order:             required_packages.append(pack_num)             remaining_order -= pack_num             found = True             break      if not found:         break 

But this will lead to the wrong result:

1x9 + 1x3 remaining: 1


So, you need to fill the order with the packages such that the total price is maximal? This is known as Knapsack problem. In that Wikipedia article you'll find several solutions written in Python.

To be more precise, you need a solution for the unbounded knapsack problem, in contrast to popular 0/1 knapsack problem (where each item can be packed only once). Here is working code from Rosetta:

from itertools import product   NAME, SIZE, VALUE = range(3) items = (     # NAME, SIZE, VALUE     ('A', 3, 5),     ('B', 5, 9),     ('C', 9, 16))  capacity = 13   def knapsack_unbounded_enumeration(items, C):      # find max of any one item     max1 = [int(C / item[SIZE]) for item in items]     itemsizes = [item[SIZE] for item in items]     itemvalues = [item[VALUE] for item in items]      # def totvalue(itemscount, =itemsizes, itemvalues=itemvalues, C=C):     def totvalue(itemscount):         # nonlocal itemsizes, itemvalues, C          totsize = sum(n * size for n, size in zip(itemscount, itemsizes))         totval = sum(n * val for n, val in zip(itemscount, itemvalues))          return (totval, -totsize) if totsize <= C else (-1, 0)      # Try all combinations of bounty items from 0 up to max1     bagged = max(product(*[range(n + 1) for n in max1]), key=totvalue)     numbagged = sum(bagged)     value, size = totvalue(bagged)     size = -size     # convert to (iten, count) pairs) in name order     bagged = ['%dx%d' % (n, items[i][SIZE]) for i, n in enumerate(bagged) if n]      return value, size, numbagged, bagged   if __name__ == '__main__':     value, size, numbagged, bagged = knapsack_unbounded_enumeration(items, capacity)     print(value)     print(bagged) 

Output is:

23 ['1x3', '2x5'] 

Keep in mind that this is a NP-hard problem, so it will blow as you enter some large values :)


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: