How to allocate a number of items to unevenly sized sets of evenly sized boxes within each set so that each box is filled and all items are allocated?

Question

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?

Answer 1

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.

See also this other answer.

Answer 2

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.

Answer 3

Here is how we ended up solving it:

Python:

def allocate_items_to_boxes(
    total_items: int,
    box_sizes: Iterable[tuple[Hashable, int] | int],
) -> dict[Hashable, int]:
    if total_items == 0:
        return {}

    box_sizes = list(box_sizes)

    try:
        box_size_id, box_size = box_sizes[0]
    except TypeError:
        box_size = box_sizes[0]
        box_size_id = box_size

    max_boxes = total_items // box_size
    box_sizes_rem = box_sizes[1:]

    for boxes in range(max_boxes, -1, -1):
        total_items_rem = total_items - boxes * box_size

        try:
            solution = allocate_items_to_boxes(total_items_rem, box_sizes_rem)
        except (ArithmeticError, IndexError):
            continue

        solution[box_size_id] = boxes
        return {k: v for k, v in solution.items() if v}

    raise ArithmeticError()

This tries to allocate as many items as possible to the first sizes in box_size, which works out quite well for our use case. Most items should be allocated to the box size with the cheapest item price.

This function prioritizes lowest prices and handles fractions:

def optimize_variant_unit_quantity(
    variant: ProductVariant,
    quantity: int,
) -> dict[str | None, Decimal]:
    unit_types = list(UnitPriceInfo.parse_variant(variant).values())
    # Sort by "price per item (cheapest first)" and "items per unit (biggest first)":
    unit_types.sort(key=lambda x: (x.price_net / x.qty_per_unit, -x.qty_per_unit))

    decimal_places = max(
        abs(min(0, ut.qty_per_unit.normalize().as_tuple().exponent))
        for ut in unit_types
    )
    mult = 10 ** decimal_places
    d_mult = Decimal(mult)
    quantity = quantity * mult

    allocations = allocate_items_to_boxes(
        total_items=quantity,
        box_sizes=(
            (ut.id, int((ut.qty_per_unit * d_mult).to_integral_exact()))
            for ut in unit_types
        ),
    )

    return {k: (Decimal(v) / d_mult).normalize() for k, v in allocations.items() if v}

We need to run this both on the server and the browser so keeping the code as similar as possible between programming languages is best.

Typescript

class BoxAllocationError extends Error {}
class BoxSizesEmpty extends BoxAllocationError {}

function allocateItemsToBoxes(
  total_items: number,
  box_sizes: [string, number][],
): Record<string, number> {
  if (total_items === 0) {
    return {}
  }

  const next_box_size = box_sizes[0]
  if (next_box_size == undefined) {
    throw new BoxSizesEmpty()
  }
  const [box_size_id, box_size] = next_box_size
  const max_boxes = Math.floor(total_items / box_size)
  const box_sizes_rem = box_sizes.slice(1)

  for (let boxes = max_boxes; boxes > 0; --boxes) {
    const total_items_rem = total_items - boxes * box_size

    let solution: Record<string, number>
    try {
      solution = allocateItemsToBoxes(total_items_rem, box_sizes_rem)
    } catch (e) {
      if (e instanceof BoxAllocationError) {
        continue
      }
      throw e
    }

    solution[box_size_id] = boxes
    return solution
  }

  throw new BoxAllocationError()
}