13

The problem is that I have X items of varying weighted values that must go into Y containers. The containers are of differing sizes (e.g. hold differing maximum weights). The total load of each container must be approximately equivalent to the others, but the containers don't need to be full or minimized. All of the containers must be used.

This reminds me of the "knapsack" problem, but I have multiple knapsacks of differing sizes and the loads between them all must be relatively equivalent (e.g. one knapsack may only hold 12 pounds, and another knapsack may only hold 8 pounds, but they both need to be filled with the same percentage of total weight they can carry). It also reminds me of the "bin packing" problem, but that doesn't deal with the varying bin sizes or that the bins don't need to be full or minimized, they just need equivalent loads and all of them need to be used.

Can anyone please point me in the right direction as to the name of this problem within data structures and algorithm theory? I'd also be interested in any algorithms or heuristics that may be commonly used to solve a problem like this or info about the possible time complexity.

Improve this question
13
  • 1
    knapsack problem or packing problem Commented Dec 11, 2010 at 3:13
  • 1
    It's definitely in the class of optimization problems, but it's a generalization of the knapsack problem (in which case it may have a better name), not the knapsack problem itself, and the packing problem typically attempts to optimize for a minimum with a uniform set of objects, this is minimizing the standard deviation with a heterogeneous set of objects. Commented Dec 11, 2010 at 3:19
  • Please note: this isn't a "homework" problem or any such thing. Its an actual "real world" problem that I need to code a solution for, but I'm having difficulty designing an effective algorithm on my own or finding a similar problem description. Commented Dec 11, 2010 at 3:20
  • 1
    actually it sounds more like subset sum or partition (because given that all the objects must go into the containers, and given that the proportions should be equivalent, we can actually find out the "ideal" weight per container). Commented Dec 11, 2010 at 3:26
  • 1
    Can you quantify "approximately equivalent"? eg you could use the variance of the weights or alternatively the maximum difference in weights. Once this has been clarified, you might be able to frame the problem as a linear programming or quadratic programming problem. Commented Dec 11, 2010 at 4:12

2 Answers 2

Reset to default
2

Sounds like multiple-knapsack to me. From Wikipedia:

If we have n items and m knapsacks with capacities Wi, we get the multiple knapsack problem

EDIT: Sorry, missed the bit about each container needing to be similarly loaded. Still, it smells like multiple-knapsack, albeit with an extra constraint.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

And minus one, though. I agree that it smells like multiple-knapsack, but knapsack has two-dimensional objects with associated costs (or size) and values, where you optimize for max(value), min(cost); this is optimizing for maximal standard deviation over the set of knapsacks, with only one-dimensional objects (associated size).
1

If you map X to pictures of varying heights; and map Y to columns, then the solution given here should work for you too. It is a worst-fit bin packing solution with pre-sorting and additional item swapping coded in Python with examples.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.