1

I have stumbled upon the following problem: I have one list of containers with "capacities", and a list of items with quantities. I want to assign those items to the containers. The total capacity of all containers equals the total number of items.

Here is an example. That's the input:

Container A: 50
Container B: 50

Item 1: 30
Item 2: 30
Item 3: 40

Obviously, there are lots of possible solutions to this problem.

One would be a "first-fit" assignment (Container, Item, Amount):

(A, 1, 30), (A, 2, 20), (B, 2, 10), (B, 3, 40)

Another would be a "weighted distribution" assignment (not very exciting in this example, since A and B have the same capacity, but you get the idea):

(A, 1, 15), (B, 1, 15),
(A, 2, 15), (B, 2, 15),
(A, 3, 20), (B, 3, 20)

Both are (more or less) trivial to implement, and there are multiple other ways to optimize the output (optimize for minimal number of assignments, optimize for "keeping items together", etc.).

I'd like to read more about it, to compare my solution with others. Does this problem have a name, or is it "too simple"? Bin packing is similar, but not the same, since in my case I'm allowed to "split" the objects to be put in the bins.

  • 2
    I'd say this problem doesn't have a name because it isn't a problem. If any packing is valid, you don't need a complex algorithm to find valid solutions. – Hans-Martin Mosner Apr 26 '19 at 13:10
  • @Hans-MartinMosner: Valid solutions, yes, but not necessarily optimal solutions (for various definitions of "optimal"). – Heinzi Apr 26 '19 at 13:20
  • 1
    Yup, but then it becomes an optimization problem. Depending on the concrete optimality definition, it might have a specific name, but I'm not aware of a name other than "optimization problem" for this class of problems. – Hans-Martin Mosner Apr 26 '19 at 13:25
1

Your problem definition is a bit vague, however:

-If you would consider that the cost of assigning one unit of Item 1 to Container A is not the same as the cost of assigning one unit of Item 1 to Container B, then you could argue that what you are facing is a min cost flow problem.

-If you want to minimize the number of items split over multiple containers, you can probably see this as a reasonably standard bin packing problem with a fixed number of heterogeneous bins.

-If you want to minimize the total number of splits, then your problem seems to be similar to the Parallel Machine Scheduling with splitting jobs.

|improve this answer|||||

Not the answer you're looking for? Browse other questions tagged or ask your own question.