C++-一个整型数组，添加正负号，使结果最接近0

Question

一个整型数组，添加正负号，求最接近0的结果。
比如 1 2 3 ，添加符号为1+2-3=0，则最优解为0。

先枚举可行解：
f[x[1]]:=true;
f[-x[1]]:=true;
for i:=2 to n do
begin
fillchar(g,sizeof(g),0);
for j:=-40001 to 40001 do
if f[j]then
begin
g[j+x[i]]:=true;
g[j-x[i]]:=true;
end;
f:=g;
end;
再寻找可行解中离0最近的答案。。。

是否有动态规划算法？

Answer 1

有人在QQ上分享了下面这个答案，先枚举可行解：

f[x[1]]:=true;
f[-x[1]]:=true;
for i:=2 to n do
begin
fillchar(g,sizeof(g),0);
for j:=-40001 to 40001 do
if f[j]then
begin
g[j+x[i]]:=true;
g[j-x[i]]:=true;
end;
f:=g;
end;

再寻找可行解中离0最近的答案。。。

Answer 2

这个题目可以套用“将数组划分为两个元素和最接近的子数组”的方法，
首先我计算出整个整型数组的和sum，然后我现在假设有两个桶，一个是“+”桶，就是在整型数前面添加正号的桶，一个是“-”桶，就是在整型数前添加负号的桶。

你所要做的就是尽可能的在整型数组中找出一些数使得“+”桶的数字元素之和尽可能的接近sum/2;
其他没被选中的数就丢到另外一个桶中。

这么一想，是不是感觉像个特殊的0-1背包问题呢，而0-1背包问题就是典型的动态规划算法，只不过这里的价值和重量是一样的，接下来怎么做，我想你很清楚啦。。。

Answer 3

假设一个有数组个数个结点的图，每一个结点到下一个结点有两条路径（对应+和-)
于是使用最短路径法就能求出你需要的解

Answer 4

其实就是 容量为sum/2的01背包问题.
f[i][v]为前i个元素, 放入容量为v的背包 可以到达的最大重量. v<=sum/2.

可以用一维数组存 中间结果. f数组初始化为0.

for i from 1 to n
for v from sum/2 to w[i]
f[v]=max{ f[v], f[v-w[i]] + w[i] }

对于本问题, 最终结果为sum/2 - f[sum/2]

Answer 5

可以这么推：
1. 用f(n)表示前n个数添加正负号后得到的结果最接近0.并且假定数组的编号从1开始啊。
2. 则有 f(k) = f(k-1) + a[k] (if f(k-1)<0 && a[k]>0)
= f(k-1) - a[k] (if f(k-1)>0 && a[k]>0)
= 则把问题规模缩减到 a[k] 到 a[n] if( f(k)==0)

按照上面的算法写出动态规划算法即可