加减一组数字以达到一个值

Question

从浮点数向量

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

我试图找出哪些系列的"+“和"-”可以放置在每个浮点数前面，以得到一个与值GOAL尽可能接近的结果。注意，不能遗漏任何数字(必须使用所有值)。

float GOAL = 4.9;

对于这个例子，我认为最好的解决方案是

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

如果true的意思是"+“，false的意思是"-"，最好的解决方案可以表示为

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

我们只需遍历所有可能的组合。如果n是v的大小，那么就有2^n个可能的组合。随着n的增长，进程很快就会变慢(2^1000≈10^301)。

，我怎样才能写出一种搜索算法，在多项式时间内输出的不是最好的，而是下降的解？

FYI，我对搜索算法只有基本的理解。我了解启发式、贪婪算法、爬山、搜索树、极小极大博弈树等概念。

Answer 1

我只是给出一个基本的算法来做这件事。

1)计算可用浮点数的长度。(我以为长度是固定的)。

2)有一个(长度-1)的数组。所有的零。3)然后尝试在浮点数之间执行操作。(零表示负数)。4)如果数组与目标不匹配，则通过假设数组为二进制数组来增加该数目。5)重复步骤3&4，直到达到目标为止。6)即使最终不匹配，也不可能。

示例:浮动矢量大小为5。那么所有可能的操作都是

步骤2: 0000 ->(1-2-3-4-5)

步骤3: 0001 ->(1-2-3-4+5)(递增二进制数)

步骤4：((1-2-3-4+5) !=目标)- Step3。所以，0010

它将通过所有的可能性来计算。

Answer 2

不确定这是否符合你的多项式时间要求，但是遗传算法在这种优化中往往做得很好。

此外，作为实现细节，由于要添加大量浮点数字，您可能需要查看Kahan求和以最小化浮点错误。

Answer 3

我看不出有什么好办法但是..。下面的内容基于一个递归函数(一个模板函数，因此您可以将它与double和long double一起使用而不作任何更改)

#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;

 }