This is the problem:

We have 2 groups of numbers groupA and groupB. For each element in groupA you have to find one or more elements in groupB so the sum of the chosen elements in groupB equals the element from groupA. (Not posible to match one element from B with multiple elements from A, just one from A with one or more from B) We know that a solution always exist so you consume all elements in both groups.

I don't necesarly need a solution, I don't know if it exists. In fact I'm also looking for a good explanation that ther's no nice solution except using backtraking (twice). In our real problem we have more data that helps us in the matching process but in the extreme case if those aditional informations are all equal in value we end up with the described problem.

Thanks

Sounds like homework. Pass.

The problem you described does not have a nice solution - a general solution can't even use backtracking.

Let B be a series of N numbers where the n-th number is 1 + the sum of its preceeding numbers. For any number in the set A of N! numbers of all possible sums of elements of B there's one and only one subset of B summing up to that number. An algorithm that sequentially picks numbers from B cannot back track: you cannot discard any candidate summand until you have tried and summed all the (N-1)! subsets that it belongs to. And of course an algorithm that exploits the special logic of this sample B will fail on another sample.

The algorithm to find the summand of one element of A is therefore O(N!) - and so is the algorithm for finding summands for all elements of A (by simply enumerating all subsums of B)

 

That said, if this would be a real world problem - rather than a homework assignment - B is likely to be subject to constraints that you may exploit for faster solutions

Lingerance:

Sounds like homework. Pass.

 

I can't convince you is not. But if you wish put your brain at work. I don't need a pice of code here.

JdvL, as I stated in my first message we do have aditional information. Right now we want to convince others here (like the DB team) that we need more information cause there's still a small probability that we run into this scenario, even if it didn't hapend with our data sets.

I just derrived this problem, in this simplified form, from our real scenario for you guys. I invite even the one thinking this is a homework, but like this kind of chalanges, to give it a try and post something more than "Pass".

PS: sorry for double post, I failed to edit my last msg.

 Create all the 2^n possible subsets of groupB, make a hashtable that maps each sum to the corrseponding subset.Then you just have to lookup that hashtable for every entry of groupA. BTW, this challenge is a variant of the well-explored knapsack problem.

ammoQ:

Create all the 2^n possible subsets of groupB, make a hashtable that maps each sum to the corrseponding subset.Then you just have to lookup that hashtable for every entry of groupA. BTW, this challenge is a variant of the well-explored knapsack problem.

You're right it's O(2^N) not O(N!), it was too early in the morning. Other than that, creating a hashtable in 2^N passes and then looking up does not improve on just making 2^N passes. Perhaps you're making the assumption that B is always the same but that's not the OP (orginal problem).

 

ammoQ:

BTW, this challenge is a variant of the well-explored knapsack problem.

 

It's not. The knapsack is an optimization problem, this is a discrete problem. A random sample B asymptotically has a 100% probability that at most one subsum matches a target  number in A. Unlike the knapsack, one subsum is not "better" than anther. A subsum is either dead wrong or spot on. You can't make any greedy choices, like starting with large numbers or numbers close the target and converge. Failing on a subsum doesn't tell you anything: 0, 1 or N-1 elements of your failure may be part of the solution, or close to the solution. You may find a subsum that's just 1 off from the target, yet with none of its elements part of the correct solution.

Luke:

We have 2 groups of numbers groupA and groupB. For each element in groupA you have to find one or more elements in groupB so the sum of the chosen elements in groupB equals the element from groupA. (Not posible to match one element from B with multiple elements from A, just one from A with one or more from B) We know that a solution always exist so you consume all elements in both groups.

 

Does the last sentence mean that you're actually aiming to partition B and then put the sets of the partition in bijection with the elements of A?

pjt33:

Does the last sentence mean that you're actually aiming to partition B and then put the sets of the partition in bijection with the elements of A?

 

 

Well...the whole problem states that, last sentence is just that you know from start that there is (at last) a solution.

Here is an algorithm: to find a solution for one element in A.

Sort the elements in B.

Let's create a function called SumTo( int n )

which should return a set of elements from B that sum to the value or a failure code.

Start by finding the highest element that is <= n. If it is equal we have a solution. If it is less (say m ) then call SumTo( n - m ) then add our element to the result if we don't get a failure.

If we do get a failure then go to the next element < m and try again.

The only issue is that we probably can't use the same element more than once so we may need that in our SumTo algorithm. In any case we find our elements in reverse order.

For caching purposes we might want to store the sum of all the elements up to a point within B.

I could probably code this easily enough in C++ using STL.

If multiple solutions exist though it may be necessary to choose one over another one so you can complete all the elements in A. Eg:

 

A = { 15, 21, 25 }

B = { 6, 7, 8, 9, 12, 19 }

15 must be made with 7+8 to keep the 6 and the 9 free for the other numbers, and not with 6+9.

 

Cbuttius:

[...]

Given your current post count on here (2 at the time of writing, and the other post isn't <lost for words> in a 'it's not bad but...' sort of way) this looks more like a homework problem.

Cbuttius:

Here is an algorithm: to find a solution for one element in A.

Sort the elements in B.

Let's create a function called SumTo( int n )

which should return a set of elements from B that sum to the value or a failure code.

Start by finding the highest element that is <= n. If it is equal we have a solution. If it is less (say m ) then call SumTo( n - m ) then add our element to the result if we don't get a failure.

If we do get a failure then go to the next element < m and try again.

The only issue is that we probably can't use the same element more than once so we may need that in our SumTo algorithm. In any case we find our elements in reverse order.

For caching purposes we might want to store the sum of all the elements up to a point within B.

I could probably code this easily enough in C++ using STL.

If multiple solutions exist though it may be necessary to choose one over another one so you can complete all the elements in A. Eg:

 

A = { 15, 21, 25 }

B = { 6, 7, 8, 9, 12, 19 }

15 must be made with 7+8 to keep the 6 and the 9 free for the other numbers, and not with 6+9.

 

I'm sure some people think that one word per paragraph makes things easier to read.

Here's a tip: it doesn't.

Please be mindful of the other posters.

We may want to actually read what you wrote.

Thanks.

PS: This isn't IRC.

This is a forum.

Paragraphs verymuch welcome.

Doubleplusgood even.