最佳分配算法

我正在爲以下方案尋找最佳分配算法。最佳分配算法

我們有要求說18件。我在我的架子上有如下的股票。

濱A - 10 濱乙 - 6 濱Ç - 3 濱d - 4

算法應該提出以下列順序的二進制位

濱A（10），賓d（4- ），Bin C（3）

真實的情況下，我們有n個不同數量的bin。我們需要找到最佳組合。目標是最大化分配數量。

您能否請幫助。

問候， Shaju

來源

2010-04-22 shaju

歡迎來到堆棧溢出:)。如果你能告訴我們你已經嘗試了什麼以及你卡在哪裏，這將是有用的;現在聽起來你正在試圖讓我們爲你做你的功課。 – 2010-04-22 08:41:47

可能的重複：http://stackoverflow.com/questions/140406/how-can-i-programmatically-determine-how-to-fit-smaller-boxes-into-a-larger-packa – 2010-04-22 09:53:08

你的問題是類似的bin-packing problem和knapsack problem。

看看這些，看看你可以如何將這些方法應用到你的問題。

來源

2010-04-22 08:43:52 Cristina

如果這是現實世界的事情，而不是家庭作業，那麼你可能會用蠻力逃脫。嘗試所有組合的箱子，看看哪個是最好的。

在Python中，使用超集功能從http://www.technomancy.org/python/powerset-generator-python/然後：

>>> bins=[10,6,3,4] 
>>> tgt=18 
>>> max([ y<=tgt and (y,x) for (y,x) in [(sum(x),x) for x in powerset(bins)]]) 
(17, [10, 3, 4])

所以你去：最佳匹配17，通過10 + 3 + 4。那就是如果你想選擇滿箱子，那麼你可以選擇最大數量的目標。適應口味。

來源

2010-04-22 21:32:02 redtuna

如果它是現實世界事情 - 不要嘗試上面描述的暴力方式。 – 2013-05-14 12:51:24

嚴重，只是因爲算法是指數的並不一定意味着它是壞的：它真的取決於你需要的規模。這個解決方案是3行，測試你的大小是微不足道的。 10個箱子的答案是即時的，20個箱子需要10秒。只要海報的架子上不超過20個垃圾箱，這應該可以工作。 – redtuna 2013-05-15 00:45:58

-1

你可以試試這個：

第1步：
排序可用的垃圾桶由空間量
最大的箱具有指數0，最小箱已係數Z- 挑箱從指數0開始，直到整個空間不是你要找的就是你有太多的東西。如果你有你正在尋找的總數，停下來。如果沒有，繼續。

第2步。
假設您選擇的最後一個垃圾箱位於索引L處（您選擇了L + 1個垃圾箱）。現在從L降序開始，在索引L-x處交換分箱，索引爲Z-x處的分箱。通過做這些掉期，你會減少總額。在總數低於您要查找的數值之前停止交換。如果你有一個你正在尋找的總數，停止。否則進行第3步。

第3步。
假設您已經選擇了索引0和L-X之間以及Z和Z-X之間的區域，總數比您要查找的（略高）要高。現在，對於0到L-X之間的每個倉，找到索引L-X + 1和Z-X-1之間的最佳倉，您可以將它與其交換以減少總數，因此總數就是您正在查找的數量。

這個算法是線性的，給你一個很好的機會找到一組完美的箱子。

我很想聽聽這是否適合你。

來源

2015-04-18 18:24:47 Jurgen

最佳分配算法

回答

相關問題