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

e.g.

`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