CODEWITHSUNDEEP
algorithmknapsack-problemnp
Paul Clavier
Paul Clavier

Reputation: 291

Knapsack or similar with no values and with limits as to which items can be assigned where?

Say I have a number of weights which I need to spread out across a finite number of knapsacks so that each knapsack has as even a distribution of weights as possible. The catch is that different weights can only be put into the first n bags, where each value of n varies for each weight.

For example, a weight might only be able to inserted into bags up to bag 4, i.e. bags 1 through 4. Another might have a limit up to 5. The goal as previously stated is to attempt an even spread across all bags, with the number of bags set by the weight with the highest limit.

Is there a name for this problem, and what algorithms exist?

EDIT: To help visualise, say I have 4 weights:

+----------+--------+-----------+
| Weight # | Weight | Bag Limit |
+----------+--------+-----------+
|        1 |      2 |         2 |
|        2 |      3 |         3 |
|        3 |      1 |         1 |
|        4 |      2 |         4 |
+----------+--------+-----------+

A solution to the problem might look like this

| 1 |  |   |  |   |  |   |
| 2 |  | 3 |  | 2 |  |   |
|___|  |___|  |___|  |___|

Bag 1  Bag 2  Bag 3  Bag 4

Weights 3 and 1 were placed into Bag 1

Weight 2 was placed into Bag 2

Weight 4 was placed into Bag 3

Here, the load is spread as evenly as possible, and the problem is solved (although perhaps not optimally, as I did this in my head)

Hopefully this might clear up what I'm trying to solve.

Upvotes: 1

Views: 918

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

I'd describe this problem as bin packing with side constraints -- a lot of NP-hard problems don't have good names because there are so many of them. I would expect the LP-based methods for packing variable-sized bins that decompose the problem into (1) a packing problem over whole bins (2) a knapsack problem within a bin to generate candidate bins to carry over reasonably well.

Upvotes: 0

Related Questions