将整数列表分组为两组

Question

给定一个< code>n数和sum s的列表，将这些数分成< code >两个组，使得每组中的数之和小于或等于s。如果可以分组，则打印< code>YES，如果不能分组，则打印< code>NO。

例如，如果< code>n=3，s=4和< code>n数是< code>2，4，2。在这种情况下，输出为< code>YES，因为可以形成两个组< code>(2，2)和(4)。

我的解决方案如下。

A是包含n个数字的整数数组。

第一组包含第一组元素的总和。

第二组包含第二组中的元素之和。

解决方案 1

>

按降序对数组排序

继续向第二组添加数字，直到该组中的元素总和小于或等于s

将第一组的总和计算为所有元素的总和减去第二组元素的总和

如果每组元素的总和小于或等于s，则打印是，否则打印否。

    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 使用贪婪的方法

> < li >按降序对数组进行排序。

< li >将数组中的第一个元素添加到第一组。 < li >迭代其余元素，并将每个元素添加到具有最小总和的组中。 < li>

如果两组元素的总和等于< code>sum_of_all_elements，则打印< code>YES，否则打印< code>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

组 1 =

如果数字之和 =

返回true

还

返回false

Answer 2

快速尝试-A的总和必须是

你能给更多的测试用例吗？或者只是一个我的algh不起作用的案例。

Answer 3

你假设所有最小的元素都在一个组里，这不一定正确。

以下面的例子为例：

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

对于上述情况，您的两种解决方案都会产生错误的输出。

让我先澄清一下你想解决什么问题。你正试图解决子集和问题的一个修改版本。让我换个方式问你:

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难问题，不能在多项式时间内求解。然而，该问题存在一个基于动态规划的伪多项式时间算法。参见子集和问题或动态规划:子集和的伪多项式解。这个想法是这样的:

   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.

通过在构造DP时记住额外的信息，您还可以记住导致您为第一个子集选择的和S1的子集。