How to allocate a number of items to unevenly sized sets of evenly sized boxes within each set so th-CodePudding

Imagine you have a shop.
One of your products comes in boxes of 3 different sizes:
3, 5, and 10 items per box

The bigger the box, the lower the price per item. So in order to give your customer the best price, when the customer request a number of items, you want to sell them the cheapest combination of boxes each time.

This is how it should work:

# Problem 1 (easy):
total_items = 25
box_sizes = [10, 5]
box_size_allocations = {
    10: 2,
    5: 1,
}
assert allocate_items_to_boxes(total_items, box_sizes) == box_size_allocations

# Problem 2 (easy):
total_items = 35
box_sizes = [10, 1]
box_size_allocations = {
    10: 3,
    1: 5,
}
assert allocate_items_to_boxes(total_items, box_sizes) == box_size_allocations

# Problem 3 (hard):
total_items = 54
box_sizes = [10, 5, 3]
box_size_allocations = {
    10: 4,
    5: 1,
    3: 3,
}
assert allocate_items_to_boxes(total_items, box_sizes) == box_size_allocations

Originally I created a rather crude approach that simply loops through the box sizes, largest to smallest, and allocates as many unallocated items as possible to each box. Something like this:

def allocate_items_to_boxes(total_items: int, box_sizes: list):
    unallocated = total_items

    box_sizes = sorted(box_sizes, reverse=True)

    allocations = {}

    for box_size in box_sizes:
        allocations[box_size] = number_of_boxes = floor(unallocated / box_size)
        unallocated -= box_size * number_of_boxes

    if unallocated:
        raise Exception(f"{unallocated} items were not allocated to boxes!")

    return allocations

This handles problem #1 and #2 but fails on problem #3.

One idea I have, is to first find all the different permutations of possible box allocations where no item remains unallocated and then pick the cheapest one. Is that a good idea? Is there a better approach? How can I do it?

Bonus: Does the problem I described have a name?

CodePudding user response：

Unless this is some kind of assignment you can use library called Google Ortools for all kinds of combinatorial optimization problem solving. And this problem looks like a bin packing problem variant.

CodePudding user response：

This looks like a coin change problem. Here's a solution

from collections import defaultdict, Counter
def allocate_items(total_items, box_sizes):
    combos = defaultdict(list)
    combos[0] = [[]]
    for i in range(1, total_items 1):
        for x in box_sizes:
            if x<=i and combos[i-x] is not None:
                for p in combos[i-x]:
                    comb = sorted(p   [x])
                    if comb not in combos[i]:
                        combos[i].append(comb)
        if len(combos[i])>0:
            m = (min(map(len,combos[i])))
            combos[i] = [combo for i, combo in enumerate(combos[i]) if len(combo) == m]
        else:
            combos[i] = None
    return [Counter(x) for x in combos[total_items]]

Check:

total_items = 54
box_sizes = [10, 5, 3]
allocate_items(total_items, box_sizes)
[Counter({3: 3, 5: 1, 10: 4})]

Note that there can be more than one combination of minimal length, this is why the output is a list. For instance:

total_items = 9
box_sizes = [10, 5, 4, 8, 1]

allocate_items(total_items, box_sizes)
[Counter({4: 1, 5: 1}), Counter({1: 1, 8: 1})]

Perhaps some additional specification is needed for the computation of the minimum in order to get a unique result.