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>
>> >
>> >> .
>> >> 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.
>> >
>> >
>>
>>
>> --
>> --------------------------------------------------
>> 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.
>>
>>
>
> --
> 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.
>
>
--
--------------------------------------------------
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
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.
