給定一組小于或等于 Y 的 X 數，其中可能包含重復的數：
哪種演算法為您提供其元素之和大于或等于 Y 的最大子集數，其中一個子集的任何元素都不能包含在另一個子集中，并且每個子集不能重復相同的元素。
（注意：如果在初始集合中重復了兩個數字，則每個都算作一個不同的元素）
子集可以將元素分組為二重奏、三重奏、四重奏或任何其他數字。
做兩個 for 回圈來搜索最大數字的最佳組合對雙打有效，但考慮到可以做三重奏等等，像“1 1 1 1 1 7 8”這樣的情況將被次優化
uj5u.com熱心網友回復：
您可以實施“蠻力”方法并檢查所有可能的磁區并檢查它是否滿足您的要求。這將非常簡單，但除了瑣碎的情況外，效率極低。
假設您的集合 S 中有 N 個元素 e_i，其中 0 <= e_i <= Y。選擇 numparts 作為您要嘗試創建的磁區數，其中元素 sum >= Y。假設 sum e_i >= Y，我們可以最初設定 numparts = 1，否則，顯然，答案是零。
然后，您可以通過創建一個包含 N 個元素 p_i 的陣列來生成磁區，其中 0 <= p_i < numparts。這樣的磁區不超過 numparts^N ！現在，你必須嘗試找到一個，其中對于所有 0 <= j < numparts，sum {e_i : p_i = j} >= Y。如果你找到一個，增加 numparts，如果你沒有，那么你有你的答案是您確實找到了合格磁區的最大 numparts 值。
您可以通過避免大量不具有總和 >= Y 的磁區來顯著提高這種方法的效率。S 的“只有”2^N 個不同的子集，因此總和 >=Y 的子集的數量必須更少大于或等于 2^N。對于每個這樣的子集 S_k，您可以嘗試找到 S - S_k 的最大磁區數，每個總和 >= Y，這只是同一問題的遞回。這將為您提供您正在尋找的絕對最大結果，但對于非微不足道的問題仍然是一場計算噩夢。
一種快速但次優的演算法是簡單地按升序對陣列進行排序，然后在您按順序處理排序的元素時根據磁區總和進行磁區。例如
假設 s[i] 是排序陣列中的元素，...
partitionno = 0;
partitionsum = 0;
for (i=0; i<N; i ) {
partitionsum = s[i];
if (partitionsum >= Y) {
partitionsum = 0;
partitionno ;
}
}
給 partitionno 個子集，每個子??集的總和至少為 Y。排序可以在 O(N) 時間內完成，并且上面的演算法也是 O(N)，因此您可以將其用于 1000000 或更多的 N。
uj5u.com熱心網友回復：
這是一個非常困難的 NP，因為它包含作為特例的3 磁區問題的特例，即將集合劃分為三元組，每個三元組具有相同的總和，其中所有數字都在該總和/4 到該總和/2 的范圍內。眾所周知，這種特殊情況具有很強的 NP 難度。
因此，沒有已知的演算法可以解決它，找到一個將是一件大事。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532360.html
標籤：算法数学
下一篇：滑塊輪播JS，反應