算法將數字排序成具有特定總和的集合

Question

我有27塊不同長度從18到48英寸的硬木地板條。我想製作3塊由3排地板組成的木板。兩塊木板必須長60英寸，另一塊木板長72英寸。所有條的總長度足以構建這些木板。很顯然，我可以隨機選擇這些條，將它們粘合起來並剪裁成大小。不過，我想盡量減少浪費量。

這個問題可以更簡單地重述爲：我有27個整數，並希望將它們分成9組。 6個集合中的每一個加起來爲60，其餘三個集合中的每一個加起來爲72.這個問題是子集和問題的變化。

我發現一些帖子討論「dynamic programming」但我什麼都不知道這種方法更別說如何代碼吧。

A similar問題被問了一會兒，但討論缺乏。

我的方法是'谷歌方式'。蠻力。計算一切。稍後再分類。所以，

將整數分成9個數字的3個數組。注意有9！/ 3！ = 60480分組。

爲每個組計算 每個陣列的總和，稱此爲ArraySum。其中有9個。

(A,B,C,D,E,F,G,H,I) 

計算從目標金額（72,60,60）

A-72,B-72,C-72, D-60, E-60,... 

加起來所有該組的差異和存儲數之差（稱之爲GroupSum）。這是我想要最小化的數字。

置換ArraySums和目標的款項之間的配對差異給（9！/ 3！= 60480）

現在回去，改變分組和重複。 我得到60480 x 60480 GroupSums = 3657830400

排序groupsums，找到最低的groupsum，選擇該分組。

有沒有比預先計算和排序更好的方法？

Answer 1

除非我誤解的東西，似乎無關緊要如何，只要你能找到，在所有工作的分組將它們組合（即，所有的組都至少需要的長度）

邏輯是你要開始準確的數量，意味着你無論如何都需要使用它們。你需要的長條的總長度是恆定的（60 * 6 + 72 * 3），所以你將使用的總長度（無論你的總和達到多少），所以浪費是一個常數 - 無論它們之間的差異如何是。如果我理解正確，一個貪婪的算法應該做的伎倆 - 只要使用任何組合給你每個給定木板的最小結果，任意解決關係，並繼續下一個。

除非你想最大限度地減少需要在所有切割，帶的量，即分配所有「廢」爲儘可能少帶越好。在這種情況下，你應該使用一個L0損失函數，而不是L1爲你建議（即你希望儘量減少總和的數目！= 0，而不是和本身的價值）