Expecting solution is which is independent of S
On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana wrote:
> How will you divide and array of approx 100 elements into two sub sets
> of 50 each such that the difference between both the subsets is the
> minimum possible one . .
>
> Thanks in advance .
@vishal
may be ur solution is correct
but if S very large then its not feasible to have matrix
On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana wrote:
> How will you divide and array of approx 100 elements into two sub sets
> of 50 each such that the difference between both the subsets is the
> mi
What if we sort array and place first n/4 and last n/4 elements in one
subarray and
other n/2 in the 2nd subarray.
On Fri, Dec 31, 2010 at 4:08 AM, Anand wrote:
> http://anandtechblog.blogspot.com/2010/07/partition-of-array.html
>
>
> On Thu, Dec 30, 2010 at 12:35 AM, vishal raja wrote:
>
>> Th
http://anandtechblog.blogspot.com/2010/07/partition-of-array.html
On Thu, Dec 30, 2010 at 12:35 AM, vishal raja wrote:
> This means , You can make a sum = j , with or without using the item i ,
> while calculating P[i][j].
>
> So you can have another counter Count2 which will have the count for s
This means , You can make a sum = j , with or without using the item i ,
while calculating P[i][j].
So you can have another counter Count2 which will have the count for such
items. So you will calculate P as discussed before
but You will add 1 in Count2[i][j] whenever you find that case. add one i
vishal , what will we do to count when both p[i-1][j] and
p[i-1][j-a[i]] is true .
On Thu, Dec 30, 2010 at 12:36 PM, Ankur Khurana
wrote:
> Thanks everybody for wonderful support and special thanks to Vishal
> raja. . But i was bit apprehensive about your last solution . . i will
> test it :) a
Thanks everybody for wonderful support and special thanks to Vishal
raja. . But i was bit apprehensive about your last solution . . i will
test it :) and let you know as well . Thanks . . . .
On Thu, Dec 30, 2010 at 11:52 AM, vishal raja wrote:
> But the same solution I've given above can give y
But the same solution I've given above can give you the solution for this
problem .
In the formed table of P[i][j] , you can take another variable attached to
it as count[i][j] for how many items we have selected yet.
So you gotta find , the max. value of j which has count = 50.
count[i][j] = count
yeah, My bad.
Missed that.
On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares wrote:
> Sum up all the number and divide by 2
>
> Using the algorithm subset problem to find a number close to median
>
>
> Wladimir Araujo Tavares
> *Federal University of Ceará
>
> *
>
>
>
>
>
> On Wed, Dec 29, 2010
Sum up all the number and divide by 2
Using the algorithm subset problem to find a number close to median
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana wrote:
> How will you divide and array of approx 100 elements into two sub sets
>
use dynamic programming.
Make this problem similar to knapsack one.
You want to find the items from a given array which sums up to (exactly or
nearly) S/2 (here S is total sum of all integers)
Let's say
P(i,j) is probability to make a sum = j with the first i items in the array.
P(i,j) = 1 if P(
How will you divide and array of approx 100 elements into two sub sets
of 50 each such that the difference between both the subsets is the
minimum possible one . .
Thanks in advance .
Ankur
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To
12 matches
Mail list logo
