將整數列表分組爲兩個組

Question

給定n數字和總和s的列表，將這些數字分組到two組中，使得每組中的數字總和爲less than or equal to s。如果可以分組，則打印YES，如果不能分組，則打印NO。

例如，如果n=3 , s=4和n的數字是2,4,2。 在這種情況下，輸出爲YES，因爲可以形成的兩個組爲(2,2) and (4)。

我的解決方案如下。

A是包含n個數字的整數數組。

first group包含第一組元素的總和。

second group包含第二組元素之和。

溶液1

1. 排序以降序排列。
2. 繼續向第二組添加數字，直到該組中元素的總和小於或等於s。
3. 計算用於第一組的總和減去sum of all elementssum of elements in second group

4. 如果每個組中的元素的總和小於或等於s，然後打印YES別的打印NO。

   qsort (A, n, sizeof(int),compare); 
       int second_group=0; 
       f=0; 
       for(i=0;i<n;++i) 
       { 
        if((second_group+A[i])==s) 
        { 
         f=1; 
         break; 
        } 
        else if((second_group+A[i])<s) 
        { 
         second_group+=A[i]; 
        } 
   
       } 
       int first_group=sum_of_all_elements-second_group; 
       if(f==1) 
       { 
        cout<<"YES\n"; 
       } 
       else if ((second_group<=s) && (first_group<=s)) 
       { 
        cout<<"YES\n"; 
       } 
       else 
       { 
        cout<<"NO\n"; 
       } 
   

溶液2 使用Greedy approach

1. 排序以降序排列。
2. 將數組中的第一個元素添加到第一組。
3. 迭代其餘元素並將每個元素添加到具有最小總和的組中。

4. 如果兩個組的元素的總和等於sum_of_all_elements，則打印YES否則打印NO。

   qsort (A, n, sizeof(int),compare); 
       int first_group=0,second_group=0; 
       f=0; 
       first_group=A[0]; 
       for(i=1;i<n;++i) 
       { 
        if(first_group<second_group) 
        { 
         if((first_group+A[i])<=s) 
         first_group+=A[i]; 
        } 
        else 
        { 
         if((second_group+A[i])<=s) 
         second_group+=A[i]; 
        } 
       } 
       if((first_group+second_group)==sum_of_all_elements) 
        cout<<"YES\n"; 
       else 
        cout<<"NO\n"; 
   

問題

上述兩種解決方案爲不正確的答案。我無法理解他們失敗的場景。

如果有人能幫助我解決這個問題的其他解決方案，那將是非常好的。

Answer 1

快速嘗試 - A的總和必須是< = 2 * s。A中最大的元素必須是< = s。

你可以提供更多的測試用例嗎？或者只是一個案件，當我不工作。

Answer 2

你假定所有最小的元素都在一個組中，但這不一定是真的。

看看下面的例子：

array = {1, 2, 4, 6} , s = 7 

您的解決方案，雙方將產生錯誤的輸出，用於上述情況。

讓我先澄清你想解決什麼問題。您正試圖解決Subset Sum Problem的修改版本。讓我給你解釋一下這個問題：

1. Give an array A and a sum S. Find the subset of A with the largest sum S1 
    such that S1 <= S. (We want the largest sum because it will give the 
    smallest possible sum for the rest of the elements). 

2. Now the sum of the rest of the elements is S2 = TotalSum - S1. If S2 <= S, 
    print YES otherwise print NO. 

子集和問題是一個NP難問題，不能用多項式時間求解。但是，存在一個基於動態編程的問題的Pseudo-Polynomial Time算法。對於僞多項式解，請參見Subset Sum Problem或Dynamic Programming: Subset Sum。我們的想法是這樣的：

Use dynamic programming to calculate whether there is a solution to the 
    subset sum problem for sum = S. If there is a solution, then report YES 
    if TotalSum - S <= S. Otherwise pick the largest sum that exists in the 
    DP table (just select the last row with subset sum = True entry in the 
    last column). Let this sum be S1. 
    If S1 <= S report YES otherwise NO. 

您還記得那張通往你選擇第一個子集的總和S1，通過記住額外的信息，同時構建DP的子集。

Answer 3

組別1 = <秒和第2組= <小號 所以 組1 +組=數之和= < 2 * S 所以我建議簡單的算法，

如果數之和= < 2 * S

還真

其他

返回假

Answer 4

首先對數字進行排序。第一組（sum1）由最大數量+小數組成。其他號碼轉到第二組。

如果數字總和> 2 * s返回false;

升序排序陣列

I = 1; sum1 = a [n]; SUM2 = 0;

雖然（SUM1 + A [1] = < S）

總和1 =總和1 + A [1]

我+ +

端而

對於j = i到n -1個

SUM2 = SUM2 + A [j]的

端爲

如果（SUM1 = < S）和（SUM2 = < S）返回true

否則返回false;