I dont think greedy or dp should be the way to approach the problem since it
does not show optimal sub-structure property.
On Mon, May 17, 2010 at 10:22 PM, Rohit Saraf
<rohit.kumar.sa...@gmail.com>wrote:
> I was really not able to digest the greedy thing....
> Great example!!
>
> On 5/17/10, Amir hossein Shahriari <amir.hossein.shahri...@gmail.com>
> wrote:
> > @divya : it's a greedy approach and again it's WRONG!
> > your answer for {110,100,90,70,60,10 } would be:
> > A = { 110, 70, 60 }
> > B = { 100, 90 , 10 }
> > the difference is 40
> > the correct ans:
> > A = { 110, 100 , 10 }
> > B = { 90 , 70 , 60 }
> > the difference is 0
> > i don't believe a greedy algorithm would work for this problem!
> >
> > On Mon, May 17, 2010 at 5:06 PM, Rohit Saraf
> > <rohit.kumar.sa...@gmail.com>wrote:
> >
> >> @divya : descending order sorting works. BRILLIANT !!
> >>
> >> On 5/17/10, divya jain <sweetdivya....@gmail.com> wrote:
> >> > my algo on the array 1 200 500 2000
> >> > sort the array therefore we have now 2000 500 200 1
> >> > 1st array will have largest element
> >> > A= {2000}
> >> > and B={500}
> >> > sumA=2000
> >> > sumB=500
> >> > now abs((2000+200)-500)>abs((2000)-(500+200))
> >> > so we ll put 200 in array B. now since B has n/2 elements rest of the
> >> > element goes to array which is 1.
> >> > so the ans is
> >> > A={2000,1}
> >> > b={500,200}
> >> >
> >> >
> >> > On 15 May 2010 19:10, Rohit Saraf <rohit.kumar.sa...@gmail.com>
> wrote:
> >> >
> >> >> so what will ur algo give for array 1,200,500,2000
> >> >>
> >> >> On 5/15/10, divya jain <sweetdivya....@gmail.com> wrote:
> >> >> > my approach:
> >> >> > 1. sort the array
> >> >> > 2. take a variable diff. intitialize it to 0.
> >> >> > 3. take the 1st element from array nd place it in array A and 2nd
> >> >> > element
> >> >> in
> >> >> > array B. stoe in diff sum(A)-sum(B).
> >> >> > 4. now place the next element in array A or B according to the
> >> condition
> >> >> if
> >> >> > if sum(A+element)-sum(B)> sum(a)-sum(B+element). store the
> >> >> > element
> >> >> in
> >> >> > B otherwise in A. also while storing the element in ny array
> >> >> > maintain
> >> >> the
> >> >> > count of element in that aaray. if any time the count reaches n/2
> >> where
> >> >> > n
> >> >> is
> >> >> > the no. of elements in the given aaray. then store rest element in
> >> the
> >> >> > other array.
> >> >> > 5. repeat step 5 until both array A n B get n/2 elements..
> >> >> >
> >> >> > hope my approach is clear and correct.
> >> >> > comments are welcomed.....
> >> >> >
> >> >> > On 15 May 2010 08:47, Rohit Saraf <rohit.kumar.sa...@gmail.com>
> >> wrote:
> >> >> >
> >> >> >> Choosing a greedy strategy for this would be difficult.
> >> >> >>
> >> >> >> For a simple dp you can
> >> >> >> maintain A[i,total,present] using a recurrence
> >> >> >>
> >> >> >> i is the present index of array
> >> >> >> total is the number of elements reqd in first partition.
> >> >> >> present is the no of elements already there in first partition.
> >> >> >>
> >> >> >> the array stores difference between sums. GET the minimum of all
> >> these
> >> >> >> and backtrack.
> >> >> >>
> >> >> >>
> >> >> >> On 5/15/10, Amir hossein Shahriari <
> amir.hossein.shahri...@gmail.com
> >> >
> >> >> >> wrote:
> >> >> >> > @karas: your solution is greedy and its wrong e.g. for
> >> >> >> > {1,2,3,4,5,100}
> >> >> >> your
> >> >> >> > diff would be 95 but the best result is 91
> >> >> >> >
> >> >> >> > i think we can solve this problem by dynamic programming but not
> a
> >> >> >> > simple
> >> >> >> > one! since the size of the two subsets must be equal.
> >> >> >> > so it's DP solution has at least 3 dimensions: tow dimensions
> >> >> >> representing
> >> >> >> > the number of elements in each subset and another for the
> >> difference
> >> >> >> between
> >> >> >> > their sums
> >> >> >> >
> >> >> >> > On Fri, May 14, 2010 at 10:11 PM, W Karas <wka...@yahoo.com>
> >> wrote:
> >> >> >> >
> >> >> >> >> On May 14, 4:51 am, divya <sweetdivya....@gmail.com> wrote:
> >> >> >> >> > Algorithm to partition set of numbers into two s.t. diff bw
> >> their
> >> >> >> >> > sum is min and they hav equal num of elements
> >> >> >> >>
> >> >> >> >> void part(const int a[], int n_a, int g1[], int g2[])
> >> >> >> >> {
> >> >> >> >> int i, j, k;
> >> >> >> >>
> >> >> >> >> /* diff = sum(g1) - sum(g2) */
> >> >> >> >> int diff;
> >> >> >> >>
> >> >> >> >> sort(a, n_a);
> >> >> >> >>
> >> >> >> >> diff = 0;
> >> >> >> >> for (i = 0, j = 1, k = 0; j < n_a; ++k, i += 2, j += 2)
> >> >> >> >> {
> >> >> >> >> if ((a[i] > a[j]) == (diff > 0))
> >> >> >> >> {
> >> >> >> >> g1[k] = a[j];
> >> >> >> >> g2[k] = a[i];
> >> >> >> >> }
> >> >> >> >> else
> >> >> >> >> {
> >> >> >> >> g1[k] = a[i];
> >> >> >> >> g2[k] = a[j];
> >> >> >> >> }
> >> >> >> >> diff += g1[k] - g2[k];
> >> >> >> >> }
> >> >> >> >> }
> >> >> >> >>
> >> >> >> >> --
> >> >> >> >> You received this message because you are subscribed to the
> >> >> >> >> Google
> >> >> >> Groups
> >> >> >> >> "Algorithm Geeks" group.
> >> >> >> >> To post to this group, send email to
> algoge...@googlegroups.com.
> >> >> >> >> To unsubscribe from this group, send email to
> >> >> >> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> <algogeeks%25252bunsubscr...@googlegroups.com<algogeeks%2525252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> >
> >> >> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> <algogeeks%25252bunsubscr...@googlegroups.com<algogeeks%2525252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> <algogeeks%25252bunsubscr...@googlegroups.com<algogeeks%2525252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%25252bunsubscr...@googlegroups.com<algogeeks%2525252bunsubscr...@googlegroups.com>
> <algogeeks%2525252bunsubscr...@googlegroups.com<algogeeks%252525252bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> <algogeeks%25252bunsubscr...@googlegroups.com<algogeeks%2525252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> >
> >> >> >> .
> >> >> >> > For more options, visit this group at
> >> >> >> > http://groups.google.com/group/algogeeks?hl=en.
> >> >> >> >
> >> >> >> >
> >> >> >>
> >> >> >>
> >> >> >> --
> >> >> >> --------------------------------------------------
> >> >> >> Rohit Saraf
> >> >> >> Second Year Undergraduate,
> >> >> >> Dept. of Computer Science and Engineering
> >> >> >> IIT Bombay
> >> >> >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >> >> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >> >> >>
> >> >> >> --
> >> >> >> You received this message because you are subscribed to the Google
> >> >> Groups
> >> >> >> "Algorithm Geeks" group.
> >> >> >> To post to this group, send email to algoge...@googlegroups.com.
> >> >> >> To unsubscribe from this group, send email to
> >> >> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> <algogeeks%25252bunsubscr...@googlegroups.com<algogeeks%2525252bunsubscr...@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 algoge...@googlegroups.com.
> >> >> > To unsubscribe from this group, send email to
> >> >> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@googlegroups.com>
> >
> >> >
> >> >> .
> >> >> > For more options, visit this group at
> >> >> > http://groups.google.com/group/algogeeks?hl=en.
> >> >> >
> >> >> >
> >> >>
> >> >>
> >> >> --
> >> >> --------------------------------------------------
> >> >> Rohit Saraf
> >> >> Second Year Undergraduate,
> >> >> Dept. of Computer Science and Engineering
> >> >> IIT Bombay
> >> >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >> >>
> >> >> --
> >> >> You received this message because you are subscribed to the Google
> >> Groups
> >> >> "Algorithm Geeks" group.
> >> >> To post to this group, send email to algoge...@googlegroups.com.
> >> >> To unsubscribe from this group, send email to
> >> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@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 algoge...@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> >> .
> >> > For more options, visit this group at
> >> > http://groups.google.com/group/algogeeks?hl=en.
> >> >
> >> >
> >>
> >> --
> >> Sent from my mobile device
> >>
> >> --------------------------------------------------
> >> Rohit Saraf
> >> Second Year Undergraduate,
> >> Dept. of Computer Science and Engineering
> >> IIT Bombay
> >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
> --
> Sent from my mobile device
>
> --------------------------------------------------
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Thanks & Regards,
- NMN
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
