-3

假设我有 number x、 list of numbers 和 max number y。我需要找到可以通过添加x列表中每个元素的加法或减法获得的最大结果，以使总和不超过y也不低于 0。

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

例子：

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

Max i can get : 3 - 2 + 6 +1 = 8 which is less than 10 and >0
failure case for this will 3+2+6+1= 12 is which is > y so is invalid solution。
另一个失败案例 3-2-6 = -5 （这里不需要检查 6 之后的元素，因为你得到了 -ve number 被拒绝）

我怎样才能找到这个最大值？

4

2 回答 2

3

所以，你基本上有一个 listl和一个 number y-x（如果你必须 addx和 get y，很容易看出它等同于 get y-x）并且你想要添加/减去每个元素l并尽可能接近 value y-x。

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

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

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

于 2012-11-12T21:56:15.653 回答
0

这是解决方案：

    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}）

于 2012-11-12T22:18:06.243 回答