Adding and subtracting a set of numbers to reach a value

Question

From a vector of float numbers

``````std::vector<float> v { 0.32, 0.0004, 12.78, -9.2, 1.1 };
``````

I am trying to find out what series of "+" and "-" one can place in front of each float number to get a result that is as close as possible as the value `GOAL`. Note that no number can be left out (all values must be used).

``````float GOAL = 4.9;
``````

For this example, I think the best possible solution is

``````+ 0.32 - 0.0004 + 12.78 + (-9.2) + 1.1 = 4.9996
``````

Let `true` mean "+" and `false` mean "-", the best possible solution could be represented as

``````std::vector<bool> solution { true, false, true, true, true }
``````

One could just iterate through all possible combinations. If `n` is the size of `v`, then there are 2^n possible combinations. As `n` grows large, the process becomes quickly very slow (2^1000 ≈ 10^301).

How could I go about writing a search algorithm that would output not the best but a descent solution in polynomial time?

FYI, I have only basic understanding of search algorithms. I understand the concepts of heuristic, greedy algorithm, hill climbing, search tree, minimax game tree and others for examples.

Show source
2017-01-02 14:01 5 Answers

Answers to Adding and subtracting a set of numbers to reach a value ( 5 )

1. not sure if this conforms to your polynomial time requirement, but genetic algorithms tend to do pretty well in this kind of optimization.

also, as an implementation detail, since you are going to add up a large number of floating point numbers, you might want to look into Kahan summation to minimize floating point error.

2. I am just giving a basic algorithm to do this.

1) Calculate the length of available float numbers. ( I assumed length is fixed ).

2) Have an array of the (length-1). with all zeros. 3) Then try to perform operation between the floating numbers.( Zero refers negative ). 4) If it was not matching to GOAL, then increment the number by assuming the array as binary one. 5) Repeat step 3 & 4 until it matches GOAL. 6) Even at end if it is not matched , there is no possibility.

Ex : Floating vector size is 5. Then the all the possible operations are

Step 2: 0000 --> (1st - 2nd - 3rd - 4th - 5th)

Step 3: 0001 --> (1st - 2nd - 3rd - 4th + 5th) (Incremented binary num)

Step 4: ((1st - 2nd - 3rd - 4th + 5th) != GOAL ) --> Increment and call Step3. So, 0010

It will calculate via all the possibility.

3. See if this is sufficient:

``````//For specifying the nature of the sort
//It indicates the sort will be performed in descending order based on
//Absolute magnitudes of the values
bool type(const pair<float,int>& a,const pair<float,int>& b)
{
if(abs(a.first)>abs(b.first))
return 1;
else
return 0;
}

int main()
{
float a[]={0.32,0.0004,12.78,-9.2,1.1};  //Array of numbers
vector<pair<float,int> > v;  //Vectors of pairs: value,index
int solution[5]={0};      //Resultant sequence
for(int i=0;i<5;i++)    //Storing value and index as pairs in the vector
v.push_back(make_pair(a[i],i));
float goal=4.9;
float sum=0;
//STL sort to sort in descending order based on absolute magnitudes
sort(v.begin(),v.begin()+5,type);
for(int i=0;i<5;i++)
{
if(sum<goal)
{
sum+=abs(v[i].first);
if(v[i].first<0)
solution[v[i].second]=0;
else
solution[v[i].second]=1;
}
else
{
sum-=abs(v[i].first);
if(v[i].first<0)
solution[v[i].second]=1;
else
solution[v[i].second]=0;
}
}
cout<<sum<<endl;         //For debugging
for(int i=0;i<5;i++)     //For debugging
cout<<solution[i]<<endl;
}
``````

Now the above code sorts the array in descending order of the values given in the pairs. Note that it sorts based on absolute magnitude. So 10,8,-9 will be sorted as 10,-9,8. Since, after sorting the original positions change, keys are assigned to them, which are nothing but array index.
The solution array is the same as your solution vector.
If the sum is smaller than the goal, the absolute value of the current pair in the vector is added to the sum. Else the absolute value is subtracted.

4. I don't see an elegant solution but... the following is based on a recursive function (a template function, so you can use it with `double` and `long double` without changes)

``````#include <cmath>
#include <vector>
#include <iostream>

template <typename F>
F getSol (std::vector<F> const vals, F const & goal,
std::vector<bool> & sol, std::size_t const & used,
F const & sum)
{
F  ret;

if ( used == vals.size() )
{
ret = sum;
}
else
{
std::vector<bool> sol1 { sol };
std::vector<bool> sol2 { sol };

sol1.push_back(true);
sol2.push_back(false);

F ret1 { getSol(vals, goal, sol1, used+1U, sum+vals[used]) };
F ret2 { getSol(vals, goal, sol2, used+1U, sum-vals[used]) };

if ( std::fabs(ret1 - goal) < std::fabs(ret2 - goal) )
{
ret = ret1;
sol = std::move(sol1);
}
else
{
ret = ret2;
sol = std::move(sol2);
}
}

return ret;
}

int main()
{
std::vector<float> v { 0.32, 0.0004, 12.78, -9.2, 1.1 };
std::vector<bool>  solution;

float goal { 4.9f };

float res { getSol(v, goal, solution, 0U, 0.0f) };

std::cout << "the result is " << res << std::endl;
std::cout << "the solutions is ";

for ( auto const & b : solution )
std::cout << b << ", ";

std::cout << std::endl;

}
``````
5. We can think about a greedy algorithm, which gives a descent solution in O(n) time.

Algorithm :

Let the array and goal be :

``````vector<float> v { 0.32, 0.0004, 12.78, -9.2, 1.1 };
float GOAL = 4.9;
``````

Now start iterating the vector from the first index, and greedily choose the sign, i.e.

``````If  "+" :
diff = |Goal- ValueTillNow| = |4.9-0.32| = 4.58
If  "-" :
diff = |Goal- ValueTillNow| = |4.9-(-0.32)| = 5.22
``````

Now since we want the `ValueTillNow` to be as close to the Goal we will greedily choose "+" for first float.

Now go similarly for rest index in array. Update `ValueTillNow`. Calculate the diff for two options i.e. `"+"` and `"-"` and choose the one with leads closer to GOAL.

Time Complexity : O(n)