算法優化組值列表

我有幾個數字。我需要將它們分成幾組，以便一組中所有數字的總和在預定義的最小值和最大值之間。關鍵是要儘可能少地將數字分開。算法優化組值列表

Input: 
    min, max: range for sum of numbers 
    N1, N2, N3 ... Ni: numbers to group 
Output: 
    [N1,N3,N5],[Ni,Nj,Nk,Nm...]...: groups where sum of numbers is between min and max 
    Na,Nb,Nc...: numbers, left ingrouped.

來源

2011-07-25 F0RR

這不是問題;這是一個工作描述。你有什麼嘗試？什麼沒有用？ –

只是要清楚：很少的數字未分組，或未分組數的最小累計值？你寧願留下一個3？或兩個1？ –

如果你不擔心效率，簡單地生成每一個可能的分組，並選擇一個是在你所描述的感覺正確的和最佳的。顯然，這適用於任何有限的數字列表（根據定義，它是最優的）。

如果需要提高效率，問題似乎變得更加困難。：D我會繼續思考。

編輯：來想一想，這個問題似乎至少與「子集總和」一樣難，因此，我不認爲有一個解決方案明顯比我給予的解決方案更好（即，沒有已知的多項式時間算法可以解決這個問題，如果它是NP-Hard

來源

2011-07-25 13:59:18 Patrick87

這個問題可以看作是垃圾箱的大小爲max，有一個有趣的目標：最小化沒有包裝進垃圾箱的項目的數量min。裝箱文獻中的一個想法是，「小」物品（在這種情況下，相對於max - min較小的物品）很容易打包，但對大部分組合爆炸的可能性負責，因此一些近似算法爲了裝箱做一些事情聰明的大項目，然後填寫小。另一種減少可能性的方法是將數字四捨五入成爲一個較小的集合。如何做到這一點對於垃圾箱來說是非常明顯的（整理），但不清楚該如何解決這個問題。

好的，我將舉例說明這些想法如何實例化。假設max = 1，min = 1/2。讓我們嘗試找到一個解決方案，當max = 2和min = 1/2時，這個解決方案與最佳值相競爭。（這可能聽起來很糟糕，但這種近似保證OPT在更高的標準下有時會被用於文獻中。）

首先將每個項目的大小設置爲2的冪。非常大的項目，大小爲4或更高，不能打包。大型物品，大小爲2或1或1/2，都有自己的垃圾箱。尺寸爲1/4或更小的小件物品的處理如下。只要兩個尺寸等於或小於1/4的項目具有相同的尺寸，將它們合併爲一個超級項目。將所有尺寸爲1/2的新物品裝入自己的箱子中。其餘的總尺寸小於1/2。如果另一個垃圾箱中有空間，請將它們放在那裏。否則，給他們自己的垃圾箱。

對於max = 2，所得解決方案的質量至少與OPT的max = 1的質量一樣好。對於max = 1並圍繞項目大小採取最佳解決方案。壞箱的設置保持不變，因爲沒有物品更小，並且每個箱子的存儲量小於2，因爲每個物品的尺寸小於以前的尺寸的兩倍。現在，足以證明我給出的2的冪的包裝算法是最優的。我將把它作爲一個練習。

我不認爲這會立刻推廣到一個完整的算法。我必須回去工作，但我會採取的做法是強制OPT處理最大值= 1，而ALG獲得使用max = 1 + epsilon，替代（1 + epsilon）的冪數四捨五入的步驟，然後找出如何打包小項目，可能使用動態程序，因爲貪婪可能無法工作。

來源

2011-07-25 15:04:35 insomniac

+1（我贊成這個），但你可以發展多一點？ –

@Ricky Bobby我希望你找到我的編輯有用。通過閱讀我的答案，我想主要想法是通過比較算法與更受限制的最佳值來測量近似最優性。我希望F0RR的用例可以。 – insomniac

thx我很高興看看它 –

算法優化組值列表

回答

相關問題