As some have said, this is NP, so for larger values of N it takes a
very long time. For N=20 it runs quite quickly.
// True if some set of strengths from s[n] sum to t
bool divide(unsigned int *s, int n, int t)
{
if (t == 0) return true; // We reached the goal
if (n == 0) return false; // No people left to assign
if (*s > t) return false; // Smallest person exceeds goal
if (*s * n < t) return false; // Everyone else can not total
to goal
if (divide(s+1,n-1,t)) return true; // Consider not including first
person in line
return divide(s+1,n-1,t-*s); // Consider including first
person in line
}
int main(int argc, char* argv[])
{
const int MAX=50;
int N;
unsigned int strength[MAX];
int sum = 0;
int i,j;
printf("How many people are playing?");
scanf("%d",&N);
for(i = 0; i < N; ++i)
{
printf("Enter strength of person %d:", i+1);
scanf("%d", &strength[i]);
sum += strength[i];
}
if (sum % 2 == 1)
{
printf("NO\n");
}
else
{
// Sort from high to low
for(i = 0; i < N; ++i)
for(j = 1; j < N; ++j)
{
if (strength[j] > strength[j-1])
{
strength[j] ^= strength[j-1];
strength[j-1] ^= strength[j];
strength[j] ^= strength[j-1];
}
}
if (divide(strength+1,N-1,sum/2)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
On Jul 30, 4:44 am, sylvester <[email protected]> wrote:
> input consists of N integers, separated by a space. The ith integer
> indicates the strength of the ith person.
> For each case, output "YES" if it is possible to pick some people from
> the group and separate into two teams of equal strengths else "NO"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
