HI, im having problems with the following algorithm:
Given n integer numbers, find combinations between them of sums and differences that totalize an objetive value Z. The program should have as input the n numbers and the objetive value Z, the output must be the combinations of numbers with their operators.
I dont know how to do it, I need a clue or something like that.
Thanks...
> HI, im having problems with the following algorithm:
The following is no algorithm; it's an assignment.
> Given n integer numbers, find combinations between
> them of sums and differences that totalize an
> objetive value Z. The program should have as input
> the n numbers and the objetive value Z, the output
> must be the combinations of numbers with their
> operators.
I don't quite understand. Could you give some examples?
more info please
n values sum to z. Must you use all n exactly? are subsets allowed? are duplicates allowed (more than n, but chosen from the same n)
recursion is most typically used in divide and conquer. Reduce a big problem to a smaller subproblem.
Suppose you must use all n numbers and only the n numbers.
Each number can show up in the sum in two ways either positive or negative.
so take the first number from the collection call it a. Suppose it showed up in the positive form. what must the other n-1 numbers add up to if the result of all n is Z?
suppose it showed up in the negative form, what must the other n-1 numbers add up to.
Take the problem of deciding the signs on all n numbers, fix one number and solve the problem of deciding the sign on n-1 numbers.
divide and conquer.
Thanx for the reply, I forgot to say :-P, you can use all n numbers as you can use just a part of them, and a number can't be taken twice, also the n numbers must be positive. An example:
These are the n numbers: (4,2,8,13) and I want a combination of numbers that sums 3, so the combination would be (-2,-8,13).
I was trying with the backtracking method but i couldn't get anything.
I'll try with divide and conquer to see what I get.
Thanks
Message was edited by:
rafael_josem
Message was edited by:
rafael_josem
Message was edited by:
rafael_josem
Each number has weight -1, 0 or 1.
For my own amusement and practice at functional programming I present a solution in SML.
fun foo([], 0, ys, s) = ys::s
| foo([], z, ys, s) = s
| foo(x::xs, z, ys, s) = foo(xs, z, 0::ys, foo(xs, z-x, x::ys, foo(xs, z+x, ~x::ys, s)));
fun solve(numbers, target) = foo(numbers, target, [], []);