Computer Science Canada

ANSI C backtracking Need Help
Author:  eViruS [ Mon Feb 28, 2011 1:51 pm ]
Post subject:  ANSI C backtracking Need Help
Hi guys , I have a problem to write maybe simple program.
I got number N and number D and two guys. N is number of thinks , D is number of worth of this things.

Program must give theese two guys that same amount of worth that things.

For exaple we give number N = 7 so we got 7 numbers which are worth or N's):
INPUT
6
13
8
5
4
3
1
Now if amount of all this numbers are divisible by 2 program goes foward (if not it printf "NO")
program sort this numbers for TWO guys in such a way that they has that same amount of N numbers

Somethink like that "

OUTPUT

First guy : 13 4
Sec guy : 8 5 3 1

In INPUT it must printf numbers form the biggest to the smallest as u see.

I stoped on this and i dont have any idea how to do this right.






Quote:

#include<stdio.h>
int reku(int result, int tab[], int tab1[])
{
int i;
for(i=0; i<=result ; i++)
{
if (tab[i]==tab1[i])
{
printf("%i,%i" , tab[i] ,"\n" ,tab1[i]);
}
else BackTracking(i-1);
}
}
int main(int tab[], int tab1[],int bufor[])
{
int n, i ,result;
scanf("%i" ,&n); // Number of things
result=1;
i=1;
while (i<n)
{
i++;
result=result*i;
}
for(i=0; i<n; i++)
{
scanf("%i" ,tab[i]);

}
int z=0;
for (i=0; i<n ; i++)
{
z+=tab[i];
}
if (z%2==0)
{
for(i=0 ; i<result ; i++)
{
tab[i]=tab1[i];
reku(result);
}
}
else
{
printf("NO");
}
}


Author:  DemonWasp [ Mon Feb 28, 2011 3:53 pm ]
Post subject:  RE:ANSI C backtracking Need Help
Note: this problem is often impossible for a given input. For example, consider the input:
code:
N = 2
D[] = 4, 2


The sum (6) is even, but the most even possible division is to give one person 4 and the other person 2.

Your problem can be restated as follows, which may make it easier to work on:

Given some number, N, of objects, with values D(0) to D(n-1) and sum of values S, find a set of objects that has value exactly S / 2.

Once you have one set with value exactly S / 2, the other set is obvious: just use all the other elements. This will also tell you very quickly whether the problem is possible: if no such set exists, the problem has no solution.

The simplest way I can think of to implement this is to test all possible combinations of elements. You could make your program run slightly faster in some cases by noting that if D(i) > S / 2 for any i, then the problem has no solution.
Author:  OneOffDriveByPoster [ Wed Mar 02, 2011 6:27 pm ]
Post subject:  Re: ANSI C backtracking Need Help
eViruS @ Mon Feb 28, 2011 1:51 pm wrote:
Now if amount of all this numbers are divisible by 2 program goes foward (if not it printf "NO")
Is this part of the problem statement? I am not sure that the description actually says that all the items must be assigned to one or the other. Perhaps we should try to minimize the number of unassigned objects with the constraint that the value assigned to each person is equal.
Author:  eViruS [ Thu Mar 03, 2011 5:15 am ]
Post subject:  Re: ANSI C backtracking Need Help
i change code , but i need recursion which will be working like backtracking and search all possibilities to make output but i dont have any idea how to write it

code:

#include<stdio.h>

int recursion()   
{
       
               
}



int main(int tab[], int tab1[],int bufor[])
{
int n, i;
scanf("%i" ,&n);  // Number of thinks


}
for(i=0; i<n; i++)
{
        scanf("%i" ,tab[i]);
       
}

int z=0;
for (i=0; i<n ; i++)
{
        z+=tab[i];
}
if (z%2==0)
{
        for (       )
        {

           here recursion


               
                int t,suma=0,suma1=0;
                for (t=0 ; t<n ; t++)
                {
                        suma=suma+tab[t];
                }
                for (t=0; t<n ; t++)
                {
                        suma1=suma1+tab2[t];
                }
                        if (suma==suma1)
                        {
                                printf ("%i%i" , tab[i] ,"\n" , tab2[i]);
                        }
                                else
                                {
                                        printf("NO");
                                }
        }
}
else
        {
                printf("NO");
        }
}
       
       
Author:  eViruS [ Sun Mar 06, 2011 5:11 am ]
Post subject:  RE:ANSI C backtracking Need Help
Where is last post form some guy? He really help me but i need that advices to write it ?
Author:  OneOffDriveByPoster [ Sun Mar 06, 2011 4:51 pm ]
Post subject:  Re: RE:ANSI C backtracking Need Help
Recursion basics:
establish base case (how will your recursion terminate?)
establish recursive cases (how will your recursion make progress?)

What you do need for your problem?
Try all reasonable possibilities

How can you do that?
For each item, assign to one or the other of the people; figure out if the end result is a solution.

You need to figure out how to do that with your recursion.
Backtracking would be free with help from the call stack.
Author:  eViruS [ Mon Mar 07, 2011 8:40 am ]
Post subject:  Re: ANSI C backtracking Need Help
ok thanks for help , i need 2 days and i will made it Wink

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy