Fill order from smaller packages?

Question

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

Answer 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 :)