CODEWITHSUNDEEP
algorithmknapsack-problem
Taran Goel
Taran Goel

Reputation: 468

Multiple Knapsack where items can't be reused and have different value for different knapsack

I have a problem where:

  1. There are multiple knapsack

  2. There is a fixed set of items , SuperSet you can say

  3. Every Knapsack have a specific subset of items

  4. One item can only be put into one knapsack and can't be reused

  5. Each item have different value for different knapsack

  6. Weight of every item is same but value differs according to knapsack

Now I need to distribute items in a way that my final Sum of Knapsacks is the highest.

Some Additional Details:

I'll provide bounty once Stack Overflow allows me too to the right answer even if its before! In a very crucial fix here.

Upvotes: 0

Views: 1966

Answers (2)

Lior Kogan
Lior Kogan

Reputation: 20618

This is the maximum generalized assignment problem with a specific relaxation (Weight of every item is same but value differs according to bin).

This relaxation is important: since weight of each item is same but value differs according to knapsack, you can normalize all weights to '1' by dividing the capacity of each knapsack according to the weight of its items.

Now it becomes the multiple subset-sum problem, with a slight difference: the capacity of each knapsack is different.

This problem had been studied in "A PTAS for the Multiple Subset Sum Problem with different knapsack capacities" [Caprara, Kellerer, Pferschy] 1999, where a polynomial-time (1 − ε)-approximation algorithm is given. Another approximation scheme is given in "Approximating the 0–1 Multiple Knapsack Problem with Agent Decomposition and Market Negotiation" [Smolinski] 2003.

An exact algorithm is given in "ALGORITHM 632 - A Program for the 0-1 Multiple Knapsack Problem" [Martello, Toth] 1985. A Fortran (sorry...) code can be found here.

Upvotes: 3

gnasher729
gnasher729

Reputation: 52538

It's a more complicated version of the Knapsack problem, which means it is NP complete, which means there is no solution that is guaranteed to be acceptably fast. On the other hand, being more complicated may make it easier to find an optimal solution.

The basic idea would go like this: You start with empty containers. As long as an item fits into the first container, you add it there. Then you add items to the second container, and so on. This gives you a solution which is likely not optimal. So you backtrack the last step and add a different item. If that doesn't find a better solution you backtrack the last two steps and so on. To save trying all kinds of combinations that aren't going to work anyway, you always try to calculate an upper bound for the value you might achieve, and stop examining further if that upper bound doesn't beat the known best solution.

When putting things into the first container, check for each item how much you gain by putting it into that container and not another one. Sort all the items by gain per weight. For example, if an item has a value of 40 in the first container, and 20 in another container, and weighs 2 units, that's a value of 10 per unit if you put it into the first container. An item that has a value of 40 in any container can be put anywhere. So you first put the items into the first container where that produces a gain (the idea is that this is likely to get you a good solution, and if you have one good solution then you can remove less good solutions from the search).

Don't try to make your code run fast. Try to make it easily modifiable. That's because I have no idea how well my ideas work (it's just the idea that I would start with). So you create samples, try how well the algorithm works, and then you come up with ideas how to find good solutions easier. If you keep the code easily modifiable then you can try out better ideas easily.

Upvotes: 0

Related Questions