Fill order from smaller packages?

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

You can use itertools.product:

import itertools
remaining_order = 13
package_numbers = [9,5,3]
required_packages = []
a=min([x for i in range(1,remaining_order+1//min(package_numbers)) for x in itertools.product(package_numbers,repeat=i)],key=lambda x: abs(sum(x)-remaining_order))
remaining_order-=sum(a)
print(a)
print(remaining_order)

Output:

(5, 5, 3)
0

This simply does the below steps:

1. Get value closest to 13, in the list with all the product values.

2. Then simply make it modify the number of remaining_order.

If you want it output with 'x':

import itertools
from collections import Counter
remaining_order = 13
package_numbers = [9,5,3]
required_packages = []
a=min([x for i in range(1,remaining_order+1//min(package_numbers)) for x in itertools.product(package_numbers,repeat=i)],key=lambda x: abs(sum(x)-remaining_order))
remaining_order-=sum(a)
print(' '.join(['{0}x{1}'.format(v,k) for k,v in Counter(a).items()]))
print(remaining_order)

Output:

2x5 + 1x3
0

For you problem, I tried two implementations depending on what you want, in both of the solutions I supposed you absolutely needed your remaining to be at 0. Otherwise the algorithm will return you -1. If you need them, tell me I can adapt my algorithm.

As the algorithm is implemented via dynamic programming, it handles good inputs, at least more than 130 packages !

In the first solution, I admitted we fill with the biggest package each time. I n the second solution, I try to minimize the price, but the number of packages should always be 0.

remaining_order = 13
package_numbers = sorted([9,5,3], reverse=True) # To make sure the biggest package is the first element
prices = {9: 16, 5: 9, 3: 5}
required_packages = []

# First solution, using the biggest package each time, and making the total order remaining at 0 each time
ans = [[] for _ in range(remaining_order + 1)]
ans[0] = [0, 0, 0]
for i in range(1, remaining_order + 1):
    for index, package_number in enumerate(package_numbers):
        if i-package_number > -1:
            tmp = ans[i-package_number]
            if tmp != -1:
                ans[i] = [tmp[x] if x != index else tmp[x] + 1 for x in range(len(tmp))]
                break
    else: # Using for else instead of a boolean value `found`
        ans[i] = -1 # -1 is the not found combinations

print(ans[13]) # [0, 2, 1]
print(ans[9]) # [1, 0, 0]

# Second solution, minimizing the price with order at 0

def price(x):
    return 16*x[0]+9*x[1]+5*x[2]

ans = [[] for _ in range(remaining_order + 1)]
ans[0] = ([0, 0, 0],0) # combination + price
for i in range(1, remaining_order + 1):
    # The not found packages will be (-1, float('inf'))
    minimal_price = float('inf')
    minimal_combinations = -1
    for index, package_number in enumerate(package_numbers):
        if i-package_number > -1:
            tmp = ans[i-package_number]
            if tmp != (-1, float('inf')):
                tmp_price = price(tmp[0]) + prices[package_number] 
                if tmp_price < minimal_price:
                    minimal_price = tmp_price
                    minimal_combinations = [tmp[0][x] if x != index else tmp[0][x] + 1 for x in range(len(tmp[0]))]
    ans[i] = (minimal_combinations, minimal_price)

print(ans[13]) # ([0, 2, 1], 23)
print(ans[9]) # ([0, 0, 3], 15) Because the price of three packages is lower than the price of a package of 9

Since no declaration about the object function is found, I assume your goal is to maximize the package value within the pack's capability.

Explanation: time complexity is fixed. Optimal solution may not be filling the highest valued item as many as possible, you have to search all possible combinations. However, you can reuse the possible optimal solutions you have searched to save space. For example, [5,5,3] is derived from adding 3 to a previous [5,5] try so the intermediate result can be "cached". You may either use an array or you may use a set to store possible solutions. The code below runs the same performance as the rosetta code but I think it's clearer.

To further optimize, use a priority set for opts.

costs = [3,5,9]
value = [5,9,16]

volume = 130

# solutions
opts = set()
opts.add(tuple([0]))

# calc total value
cost_val = dict(zip(costs, value))

def total_value(opt):
    return sum([cost_val.get(cost,0) for cost in opt])

def possible_solutions():
    solutions = set()
    for opt in opts:
        for cost in costs:
            if cost + sum(opt) > volume:
                continue
            cnt = (volume - sum(opt)) // cost
            for _ in range(1, cnt + 1):
                sol = tuple(list(opt) + [cost] * _)
                solutions.add(sol)
    return solutions

def optimize_max_return(opts):
    if not opts:
        return tuple([])
    cur = list(opts)[0]
    for sol in opts:
        if total_value(sol) > total_value(cur):
            cur = sol
    return cur

while sum(optimize_max_return(opts)) <= volume - min(costs):
    opts = opts.union(possible_solutions())

print(optimize_max_return(opts))

If your requirement is "just fill the pack" it'll be even simpler using the volume for each item instead.

In case you need a solution for a small number of possible

package_numbers

but a possibly very big

remaining_order, 

in which case all the other solutions would fail, you can use this to reduce remaining_order:

import numpy as np

remaining_order = 13
package_numbers = [9,5,3]
required_packages = []
sub_max=np.sum([(np.product(package_numbers)/i-1)*i for i in package_numbers])

while remaining_order > sub_max:
    remaining_order -= np.product(package_numbers)
    required_packages.append([max(package_numbers)]*np.product(package_numbers)/max(package_numbers))

Because if any package is in required_packages more often than (np.product(package_numbers)/i-1)*i it's sum is equal to np.product(package_numbers). In case the package max(package_numbers) isn't the one with the samllest price per unit, take the one with the smallest price per unit instead.

Example:

remaining_order = 100
package_numbers = [5,3]

Any part of remaining_order bigger than 5*2 plus 3*4 = 22 can be sorted out by adding 5 three times to the solution and taking remaining_order - 5*3. So remaining order that actually needs to be calculated is 10. Which can then be solved to beeing 2 times 5. The rest is filled with 6 times 15 which is 18 times 5.

In case the number of possible package_numbers is bigger than just a handful, I recommend building a lookup table (with one of the others answers' code) for all numbers below sub_max which will make this immensely fast for any input.