-4

说数组是 : 60,45,30,45,45,5,60,45,30,30,45,60,60,45,30,30,60,30,30。我需要在数组中找到总和等于180的数字，我不需要多种可能性，只有一个正确的选择是好的。如您所见，数据集中的值可能会重复。但是整个操作应该非常有效，因为数据集可能会有所不同（更多样本）。

4

5 回答 5

5

对数字进行排序。遍历小于总和的值（跳过重复项），依次从总和中减去每个值并递归求解减少的总和，从最后选择的值之后的下一个值开始。（这为您提供了递增顺序的数字。）您可以通过执行二进制搜索而不是线性搜索来加快最后（第四）级别（当您正在寻找精确值时）。

例如，排序后：

5,30,30,30,30,30,30,30,45,45,45,45,45,45,45,60,60,60,60,60
    try 5 and solve for 175:
        try 30 and solve for 145:
            try 30 and solve for 115: fail
            try 45 and solve for 100: fail 
            try 60 and solve for 85: fail
        try 45 and solve for 135:
            try 45 and solve for 95: fail
            try 60 and solve for 75: fail
        try 60 and solve for 115:
            try 60 and solve for 55: fail
    try 30 and solve for 150:
        try 30 and solve for 120:
            try 30 and solve for 90: fail
            try 45 and solve for 75: fail
            try 60 and solve for 60: success {30,30,60,60}

（如果你想找到所有的解决方案，那么不要停止成功，你也会很快找到 {30,45,45,60}。）

于 2012-10-08T11:37:38.853 回答
2

这是子集和问题的一个更简单的变体。

事实上，您希望将 4 个元素加在一起，而不是任何大小的子集，这显然意味着它可以在多项式时间内完成。

从您的示例中可以看出，数组中的所有值都是非负数，这使得使用动态编程或显式分支定界（这可能与 DP 方法或多或少的工作相同）变得相当容易，不一定按照相同的顺序完成）

于 2012-10-08T11:38:15.910 回答
2 
var someEnumerable = new int[] { 60,45,30,45,45,5,60,45,30,30,45,60,60,45,30,30,60,30,30 };
var target = 200;
var solutions = from a1 in someenumerable
                from a2 in someenumerable
                from a3 in someenumerable
                from a4 in someenumerable
                let sum = a1 + a2 + a3 + a4
                where sum == target
                select new { a1, a2, a3, a4 };

var firstSolution = solutions.First();

Console.WriteLine("Possible solution: {0}, {1}, {2}, {3}", firstSolution.a1, firstSolution.a2, firstSolution.a3, firstSolution.a4);
于 2012-10-08T11:30:18.337 回答
0

这可能有效，但解决方案可能包含四个以上的数字：

 private void button1_Click(object sender, EventArgs e)
    {
        List<int> indexes = new List<int>();
        Calculate(180, 0, 0, array, indexes);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indexes.Count; i++)
        {
            sb.Append(array[indexes[i]].ToString() + " [" + indexes[i].ToString() + "], ");
        }
        MessageBox.Show(sb.ToString());
    }

    bool Calculate(int goal, int sum, int index, int[] arr, List<int> indexes)
    {
        if (index > arr.Length - 1)
            return false;
        sum += arr[index];

        if (sum == goal)
        {
            indexes.Add(index);
            return true;
        }
        else if (sum > goal)
            return false;
        else
        {
            bool result = false;
            int count = 0;
            while (!(result = Calculate(goal, sum, index + ++count, arr, indexes)) && (index + count) < arr.Length) ;
            if (result)
            {
                indexes.Add(index);
                return true;
            }
            else
                return false;
        }

    }
于 2012-10-08T12:05:26.923 回答
0

对我来说，它看起来像背包问题，有一个额外的条件（最大重量 ==（而不是 <=）你的幻数）。可以考虑一下。 http://en.wikipedia.org/wiki/Knapsack_problem

于 2012-10-08T11:32:33.507 回答