http://www.spoj.pl/SPOJ/problems/TUG/
earlier i thought it would be easy to do it knapsack...but when i started
coding it....i feel lost.....i have failed to relate it with 0/1
knapsack......
plz tell me how this problem can be solved using dp solution of
knapsack......i mean in knapsack you form a matrix b[ ][ ] in which
b[n][w] denotes the maximum benefit with n items available having weight
exactly w.......
.....in tug of war how can we use this matrix ??
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Thu, Aug 4, 2011 at 9:55 PM, Don <dondod...@gmail.com> wrote:
> 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 <abeygau...@gmail.com> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
