我正在寻找一些想法来处理这个特定的背包问题(我相信这是一个类似背包的问题，尽管我可能会弄错)。
作为输入，我们得到一组数字，每个数字都可以是正数或负数——我们不知道。 我们必须找到这些数字总和的最小可能绝对值。 我们不必使用所有数字。我们必须按照给定数字的相同顺序进行加法(或减法)，并且我们必须从第一个数字开始(然后加上或减去后面的数字)。
例子是:
4 11 5 5 => 0
because 4+11-5-5 = 0
10 3 9 4 100 => 2
because 10-3-9 = -2
在第二个示例中，我们跳过了最后两个数字 - 因为添加下一个数字不会给我们带来更小的绝对数字。
号码数量最多可达 5,000 , 并且它们的总和不会超过 10,000
它们是整数
最佳答案
如果你要探索 5000 个数字的所有加减组合，你将不得不经历 25000−1 ≈ 1.4⋅101505 备选方案。这显然不合理。然而，由于数字之和最多为 10000，我们知道所有部分和(包括减法)都必须介于 -10000 和 10000 之间，因此不同的和可以少于 20000 个。如果您在处理 5000 个位置时只考虑不同的总和，那么您需要考虑的总和不到 1 亿个，这对于计算机来说并不算多。
示例:假设前三个数字是 5、1、1。恰好包含三个数字的可能总和是
5+1+1=7
5+1-1=5
5-1+1=5
5-1-1=3
在添加第四个数字之前，重要的是要认识到您从四次计算中只有三个独特的结果。
关于algorithm - 具体背包状，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28666088/