New bean packaging?

Question

I look at some bottle packing problem, but not exactly the same. The problem is to place n items in the minimum number of drawers without a total weight exceeding the capacity of the bins. (classic definition)

The difference is as follows: Each element has a weight and is connected , and the capacity of the hopper is dynamically determined by the minimum boundary of the elements in this hopper.

for example., I have four elements A [11,12], B [1,10], C [3,4], D [20,22] ([weight, border]). Now, if I put item A in the basket, name it b1, then capacity b1 becomes 12. Now I try to put item B in b1, but I couldn’t, because the total weight is 11 + 1 = 12, and capacity b1 becomes 10, which is less than the total weight. So, B is placed in bin b2, whose capacity becomes 10. Now put the element C in b2, because the total weight is 1 + 3 = 4, and the capacity of b2 is 4.

I do not know if this issue has been resolved in some areas with some name. Or is it a bean packaging option that has been discussed somewhere. I do not know if this is the right place to post the question, any hints are welcome!

Answer 1

NP- , . , , .

, , - , . , , - , .. . , , , , .

- , , , . . ; , , - , .

Answer 2

. , " ", , .

, Anony-mouse , ( ). , , , ; , .

, , , , , , . , "" , "bound".

:

• .

  , , (.. ), . , , , .

• .

  1 , , .

• . , - , (.. , ).

  , ; , , ; , "" .

  , () , , , .

• , , . : 3.

• ( 3- ), .

Answer 3

ILP, :

x_{i,j}, , j bin i, y_i, , bin i, c_i, bin i, s_j ( j) b_j ( j) M ( ),

minimize sum[j] y_j

subject to:
1:   for all j:
         (sum[i] x_{i,j}) = 1
2:   for all i,j:
         y_i ≥ x_{i,j}
3:   for all i:
         (sum[j] s_j * x_{i,j}) ≤ c_i
4:   for all i,j:
         c_i ≤ b_j + (M - M * x_{i,j})
5:   x_{i,j} ϵ {0,1}
6:   y_i ϵ {0,1}

• ,
• , , ( M , , , M , )
• 6. .

.

Answer 4

, , , .

NP-hard , First Fit .. .

, .

• . , .

• ()

• Check if the next element (sorted by binding) can coexist in this bin . If he can also save the item in the hopper. If then you do not try to put it in another container or create another bin for it.
• Repeat this process until all items are located . The procedure is repeated in ascending order.

I think this pretty much solves the problem. Please tell me if this is not the case. I am trying to implement the same thing. And if there are any suggestions or improvements, let me know. :) Thank you.