「鬆散」裝箱算法

-1

不能完全想到什麼就打電話這一點，所以我的谷歌搜索也來了短...「鬆散」裝箱算法

我做得有點類似於基本bin packing problem但一些絆倒我的東西變了。

倉的數目始終爲3，和所有3總是相同的尺寸（等於所有項大小的總和的1/3）
每個項目必須放置在一個箱
物品可以被「分割」成多個連續的倉，如果它們不完全適合倉。 最小化這個。

有了這三個標準（尤其是3），我不確定這個問題甚至是NP-hard，但是第四個標準使得我稱之爲「鬆散」問題。

裝箱尺寸不一定要嚴格執行。如果一件物品要比「倉庫大小」增加10％，那就沒有問題，但前提是它可以容納整個物品（不要把碎片物品弄髒）。

這是否仍然是一個結構性問題，或者我是否弄糟了我的標準，以至於它幾乎無法解決？

如果你很好奇，我用它來呈現許多（或幾個）類別（在項目）包含許多（或幾個）鏈接的3列（在箱）。

目標語言是PHP，但僞代碼現在更可取。

來源

2015-01-08 Nick F

垃圾桶問題很難解釋的原因是因爲垃圾桶數量最少。既然你看起來確實沒有真正「最小化」任何事情，我懷疑這是NP難題。有沒有保證時間_can_始終適合垃圾箱？如果是這樣，有沒有保證它可以做到沒有過度填塞？ –

實際上，我懷疑你可能只是使用貪婪算法來處理99％的案例。 –

@MooingDuck是的，箱子尺寸被設置爲物品尺寸總和的1/3，所以所有的物品都應該完全適合，但是可以在一些箱子上完成填充以減少碎裂。 –

想我會回答我自己的未來遊客着想問題...

Loop through items largest to smallest 
Does it fit wholly (overstuffing ok) in the first open bin? ...Yes 
    Place it 
...No 
    Does it fit wholly (overstuffing ok) in the next bin? ...Yes 
     Place it 
    ...No 
     Does it fit wholly (overstuffing ok) in the last bin? ...Yes 
      Place it 
     ...No 
      //Place in first open bin, expecting a fragmentation 
      Place x "units" of item until bin size reached (no overstuffing) 
      Place y "units" of item until bin size reached (no overstuffing), starting at index x into item 
      If x+y is still less than item size, place rest in last bin.

如果遞增倉造成的索引出界，它只是將其視爲一個「不」。可能不是最好的實現，但它迄今一直對我很好。顯然，這種方法固定爲3箱，但我想它可以合理擴展到更多（有限）箱。

來源

2015-01-21 00:54:15

「鬆散」裝箱算法

回答

相關問題