有效的算法，通过将给定数字添加到列表中所有元素或其补码的总和来查找最大结果

Question

假设我有数字x，数字列表和最大数字y。 我需要找到通过将x加到列表中每个元素的加法或减法中获得的最大结果，以便总和不超过y并且不会低于 0。

注意：您必须添加或减去列表中的每个元素，这意味着您不能跳过数字。

例：

x= 3 y=10  list={2,6,1}

最大值 i 可以得到：小于 10 和>0 的3 - 2 + 6 +1 = 8
失败的情况将是3+2+6+1= 12这是>y，所以是无效的解决方案。
3-2-6 = -5另一个失败情况(这里不需要检查 6 之后的元素，因为您得到了被拒绝的 -ve 编号)

如何找到此最大值？

Answer 1

所以，你基本上有一个列表l，和一个数字y-x(如果你必须加x，并得到y，很容易看出它等价于得到y-x)，你想在l中加/减每个元素，并尽可能接近值y-x。

请注意，该问题等效于分区问题，即NP-Complete，因为如果您有一个列表l，并且值y-x == 0- 您需要找到两个子列表，l1,l2这样sum(l1) - sum(l2) == 0，l1 union l2 = l这正是分区问题。

因此 - 这个问题没有已知的多项式解决方案。

我会看看指数(例如回溯)解决方案，或者相关子集和问题的伪多项式 DP 解决方案的变体。

Answer 2

这是解决方案：

int x = 3, y = 10;
var lst = new List<int>{ 1, 2, 3, 4 };
int n = (int)Math.Pow(2, lst.Count);
var lst2 = new List<List<int>>();
for (int i = 0; i < n; i++)
{
var lstCopy = new int[lst.Count];
lst.CopyTo(lstCopy);
for (int j = 1; j <= i; j *= 2)
if ((j & i) != 0)
lstCopy[(int)Math.Log(j, 2)] *= -1;
lst2.Add(lstCopy.ToList());
}
bool yes = lst2.Select(l=>x + l.Sum()).Any(l=>l > 0 && l < y);
if (yes)
Console.WriteLine(lst2.Select(l => x + l.Sum()).Where(l => l > 0 && l < y).First());

请注意，您需要检查 2^n 个整数数组，其中 n 是原始数组的长度(它是您的 {2， 6， 1})