DP approach for solving this problem.
Anand
On Fri, Jun 4, 2010 at 9:06 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
What precisely did you not understand??
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and
This is almost the most basic dp. Read some of the examples from eva
tardos. That would help.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received
What precisely did you not understand??
--
--
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
u have not sorted the array . first sort the array nd then apply the
approach. u ll get the ryt ans
On 1 June 2010 21:32, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
Using subset sum method we can solve this. It actually DP
check out Paybill question and its solution on topcoder website
@divya: but still haven't you seen Jagadish's example? It is a
counterexample to your greedy approach.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You
oh...okay...
good example...
On 3 June 2010 13:23, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
@divya: but still haven't you seen Jagadish's example? It is a
counterexample to your greedy approach.
--
Rohit Saraf
Second Year
Using subset sum method we can solve this. It actually DP
check out Paybill question and its solution on topcoder website
link : http://www.topcoder.com/stat?c=problem_statementpm=3114rd=5865
you will have a better understanding of subset sum problem after this
--
Regards
Jitendra Kushwaha
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
Try this .. i think it will work.. correct me if wrong
sort(x[0],x[n]);
ysum=y[0]=x[n-1];
ysum=z[0]=x[n-2];
j=0;
k=n-3;
l=n/2;
for(i=1;il;i++){
if(ysumzsum){
ysum+=x[k];
How about:
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 = n_a - 1, k = 0; i j; ++k, ++i, --j)
{
if ((a[i] a[j]) == (diff 0))
{
On May 17, 5:36 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
@divya : descending order sorting works. BRILLIANT !!
Not really.
Try this input: 8 6 5 5 5 1
The best partition is [8 6 1] [5 5 5] but Divya's algorithm gives [8
5 1] [6 5 5].
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
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)
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
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;
how about
1.sorting the elements
2.moving 2 pointers ; one from first and one from last
3.group the elements that the 2 pointers pointing to until the number
of elements it has grouped is less than or equal to half of the
arraysize.
On May 14, 3:53 pm, Rohit Saraf rohit.kumar.sa...@gmail.com
@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
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
17 matches
Mail list logo
