multiple knapsack problem?

327 Views Asked by At

I have a weight X. This should be distributed into multiple knapsacks w1...wY. It should be distributed to the largest knapsacks first and smallest last. Yet the optimal distribution should be found leaving ideally the smallest unused space.

Example:

X = 17 -> w7, w5 -> w7 = 3, w5 = 0 -> unused 4 (wrong)
X = 17 -> w7, w5 -> w7 = 2, w5 = 1 -> unused 2 (wrong)
X = 17 -> w7, w5 -> w7 = 1, w5 = 2 -> unused 0 (correct)

X = 15 -> w7, w5 -> w7 = 0, w5 = 3 -> unused 0 (correct)

X = 14 -> w7, w5 -> w7 = 2, w5 = 0 -> unused 0 (correct)

X = 13 -> w7, w5 -> w7 = 1, w5 = 2 -> unused 4 (wrong)
X = 13 -> w7, w5 -> w7 = 2, w5 = 0 -> unused 1 (correct)

What algorithm could be used? I think this is a variant of the knapsack problem and possibly can be solved by a variation of it? The wikipedia article also mentions this but doesn't feature a solution.


After considering the comment, I think this should solve the problem:

Given w1...wY and weight X.

w1 + w2 + ... wY = Z

X - Z = 0 -> equal distribution
X - Z = A
    A / wY = integer
        (X - wY)/wY = count wY -> start over with w1 + w2 + ...w(Y-1), X - (A * wY) = X
    A / wY = float -> start over with w1 + w2 + ...w(Y-1), X - A = X
1

There are 1 best solutions below

0
On BEST ANSWER

It seems that you want to solve an integer programming problem \begin{array} \\ x,y \in \mathbb{Z} \\ x \ge 0 \\ y \ge 0 \\ 7x + 5y -17 \ge 0 \\ 7x + 5y \to\min \end{array}