anyone plz give hint how to solve this problem !! --
Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sat, Aug 6, 2011 at 2:53 PM, Amol Sharma <[email protected]> wrote: > 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 <[email protected]> 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 <[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. >> >> > -- 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.
