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.

closed as primarily opinion-based by gnat, Bart van Ingen Schenau, BobDalgleish, Robert Harvey Apr 26 at 14:39

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 at 13:10
  • @Hans-MartinMosner: Valid solutions, yes, but not necessarily optimal solutions (for various definitions of "optimal"). – Heinzi Apr 26 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 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.

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