CODEWITHSUNDEEP
algorithmgreedy
g4ur4v
g4ur4v

Reputation: 3288

Grouping a list of integers into two groups

Given a list of n numbers and sum s, group the numbers into two groups such that sum of the numbers in each group is less than or equal to s. Print YES if grouping is possible , print NO if grouping is not possible.

For example , if n=3 , s=4 and n numbers are 2,4,2. In this case , the output is YES as two groups that can be formed are (2,2) and (4).

My solutions are below.

A is integer array containing n numbers.

first group contains sum of elements in first group.

second group containes sum of elements in second group.

Solution 1

  1. Sort the array in descending order.
  2. Keep on adding numbers to the second group till sum of the elements in this group is less than or equal to s.
  3. Calculate the sum for first group as sum of all elements minus sum of elements in second group

  4. If sum of element in each group is less than or equal to s , then print YES else print 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";
    }

Solution 2 Using Greedy approach

  1. Sort the array in descending order.
  2. Add first element in the array to first group.
  3. Iterate over rest of the elements and add each element to the group that has minimum sum.

  4. If sum of the elements of both the groups is equal to sum_of_all_elements then print YES else print 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";

Question

Both the solutions mentioned above give incorrect answer. I am failing to understand for which scenarios they are failing.

It would be great if someone can help me out with any other alternative solution to this problem.

Upvotes: 2

Views: 1805

Answers (4)

amir khan
amir khan

Reputation: 1

At first sort the numbers. first group (sum1) composes from the biggest number + as many as the small numbers. other numbers go to the second group.

if sum of numbers > 2*s return false;

Sort the array in ascending order

i =1; sum1 =a[n]; sum2=0;

While ( sum1 + a[i] =< s)

sum 1 = sum 1 + a[i]

i ++

end while

for j = i to n -1

sum2 = sum2 + a[j]

end for

If (sum1 =< s) and (sum2=< s) return true

else return false;

Upvotes: 0

amir khan
amir khan

Reputation: 1

Group1 =< s and group2 =< s so group1 +group = sum of numbers =< 2*s So I suggest the easy algorithm,

If sum of numbers =< 2*s

return true

else

return false

Upvotes: 0

Ashu Pachauri
Ashu Pachauri

Reputation: 1403

You are assuming that all the smallest elements will be in one group, which is not necessarily true.

Take the following example:

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

Both of your solutions will yield wrong output for the above case.

Let me first clarify what problem you are trying to solve. You are trying to solve a modified version of the Subset Sum Problem. Let me rephrase the question for you:

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.

Subset Sum problem is an NP- hard problem and cannot be solved in polynomial time. However, there exists a Pseudo-Polynomial Time algorithm based on dynamic programming for the problem. See the Subset Sum Problem or Dynamic Programming: Subset Sum for the pseudo-polynomial solution. The idea is like this:

   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.

You can also remember the subset that leads to the sum S1 you select for the first subset, by remembering extra information while constructing the DP.

Upvotes: 1

podliy16
podliy16

Reputation: 65

Fast try -- the sum of A must be <= 2*s. And the biggest element in A must be <= s.

Can you give more test cases? Or just a case when my algh doesn't work.

Upvotes: 0

Related Questions