從磚塊陣列創建2個等高的柱子

Question

問題聲明：

有N塊磚（a1，a2，...，aN）。每塊磚的長度爲L1，L2，...，LN）。使用提供的磚塊製作2個最高平行支柱（相同長度的支柱）。

約束：

1. 有N個磚塊。 5 < = N < = 50
2. 每塊磚的長度。 1 < = L < = 1000
3. 磚塊的長度之和= < 1000磚塊

長度不是在大小順序給出。可能有多塊磚可能具有相同的長度。不是所有的磚都必須用來創建支柱。

實施例：

第一例 -

N = 5
2，3，4，1,6-

可能集合：
（2,6）和（3,4 1）

答：8

我的方法：

尋找2個平行支柱的最大可能長度，即。地板（N/2）。然後，使用DP來查找所有可能使用所有磚塊的總和長度。從儘可能高的總數開始< = floor（N/2），我拿出構成總和的元素的一個子集。然後，再次重複DP方法來查找是否可以使用其餘元素形成相同的和。如果可以形成，那麼輸出是可能的最高總和，否則使用第一個DP，檢查可能形成的下一個最高可能總和，然後再次重複整個過程。

上述方法的問題是，它只檢查一個元素的子集以形成所需的總和。應該檢查所有可能形成所需總和的子集，然後對於每個這些子集使用剩餘的元素，如果可以形成相同的所需總和，則應該檢查它們。麻煩的是在我目前的方法中實現這一點。

第二例 -

N = 6
3，2,6，4,7，1個

可能集合：
（3，2,6）和（7,4）

答案：11

在我的代碼的問題可能依賴於在其中的元件（磚的長度）被給定爲輸入的順序來在這種情況下。有可能第一組是使用元素（3,7,1）= 11形成的，但第二組（2，6，4）不能形成sum = 11。因此，我的代碼開始尋找下一個可能的最大值總和.ie。 10這是錯誤的。

有人可以提出更好的方法或可能改進我目前的做法。

Answer 1

我認爲你可以用動態規劃解決這個問題，對於每對（x，y），你可以使用迄今爲止考慮的磚塊中的不同磚塊建立長度爲x和y的支柱。

考慮每塊磚。在開始時只有（0，0）是可能的。當你看到一塊長度爲L的磚，那麼對於每個可能的支柱（x，y），有三個後代 - （x，y）（忽略磚），（x + L，y）（使用第一支柱上的磚） ，和（x，y + L）（使用第二個支柱上的磚）。

所以在你考慮了所有的磚頭之後，你會有一長串可能的對子，你只需選擇一對長度相同且長度儘可能長的柱子。只要沒有太多不同的對（這可以從列表中刪除任何重複項），這將是實用的。

假設磚的長度是整數，最大支柱長度是1000，那麼只有1001 * 1001個可能的成對，所以這應該是實用的，事實上，如果通過具有大小的數組來存儲成對[1001,1001]並且如果對（x，y）是可能的，則將條目[x，y]設置爲1，否則設置0。

對於本示例的前幾個步驟可到達狀態是

（0,0）考慮什麼

（0,3）（3,0）（0,0）考慮3

考慮3和2的

（0,5）（2,3）（0,3）（5,0）（0,0）

可達狀態的數量起初增長非常快，但由於我們只考慮0..1000的值，我們只關心數組是否可達，我們可以使用ab來維護它們維數的排列數組1001x1001