用于在列表中查找一组等于目标的数字的算法

本文关键字：于目标 目标 算法 数字 一组 列表 查找 用于 | 更新日期: 2023-09-27 18:35:47

这就是我要做的。我有一个整数列表：

List<int> myList = new List<int>() {5,7,12,8,7};

我也有一个目标：

int target = 20;
我

正在尝试做的是找到一种方法来创建一个新的整数列表，当它加在一起时等于我的目标。所以如果我的目标是20，我需要这样的列表：

{ 12, 8 }

如果我的目标是 26，那么我将有这个：

{ 7, 12, 7 }

每个数字只能使用一次（7 使用两次，因为它在列表中两次）。如果没有解决方案，它应该返回一个空列表。有人知道我怎么能做这样的事情吗？

用于在列表中查找一组等于目标的数字的算法

>这是一个统计问题。 您希望找到具有匹配总和的所有可能组合。我可以推荐这个项目，也值得一读：

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

然后它既简单又高效：

List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };
var allMatchingCombos = new List<IList<int>>();
for (int lowerIndex = 1; lowerIndex < myList.Count; lowerIndex++)
{
    IEnumerable<IList<int>> matchingCombos = new Combinations<int>(myList, lowerIndex, GenerateOption.WithoutRepetition)
        .Where(c => c.Sum() == 20);
    allMatchingCombos.AddRange(matchingCombos);
}
foreach(var matchingCombo in allMatchingCombos)
    Console.WriteLine(string.Join(",", matchingCombo));

输出：

12,8
5,7,8
5,8,7

您可以在此处找到下面给出的所有解决方案： https://github.com/Mr-Zoidberg/Find-Possible-Combinations

1. 使用递归 

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new List<int> { 1, 2, 5, 8, 12, 14, 9 };
        Console.WriteLine($"Number of Combinations: {SumCounter(numbers, target)}");
        Console.ReadKey();
    }

    private static int SumCounter(IReadOnlyList<int> numbers, int target)
    {
        var result = 0;
        RecursiveCounter(numbers, target, new List<int>(), ref result);
        return result;
    }
    private static void RecursiveCounter(IReadOnlyList<int> numbers, int target, List<int> partial, ref int result)
    {
        var sum = partial.Sum();
        if (sum == target)
        {
            result++;
            Console.WriteLine(string.Join(" + ", partial.ToArray()) + " = " + target);
        }
        if (sum >= target) return;
        for (var i = 0; i < numbers.Count; i++)
        {
            var remaining = new List<int>();
            for (var j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
            var partRec = new List<int>(partial) { numbers[i] };
            RecursiveCounter(remaining, target, partRec, ref result);
        }
    }

2. 使用 Linq 获取子集

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new int[] { 1, 2, 5, 8, 12, 14, 9 };
        var matches = numbers.GetSubsets().Where(s => s.Sum() == target).ToArray();
        foreach (var match in matches) Console.WriteLine(match.Select(m => m.ToString()).Aggregate((a, n) => $"{a} + {n}") + $" = {target}");
        Console.WriteLine($"Number of Combinations: {matches.Length}");
        Console.ReadKey();
    }
}
public static class Extension
{
    public static IEnumerable<IEnumerable<T>> GetSubsets<T>(this IEnumerable<T> collection)
    {
        if (!collection.Any()) return Enumerable.Repeat(Enumerable.Empty<T>(), 1);
        var element = collection.Take(1);
        var ignoreFirstSubsets = GetSubsets(collection.Skip(1));
        var subsets = ignoreFirstSubsets.Select(set => element.Concat(set));
        return subsets.Concat(ignoreFirstSubsets);
    }

3. 另一种递归方法...

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };
        var result = GetSubsets(numbers, target, "");
        foreach (var subset in result) Console.WriteLine($"{subset} = {target}");
        Console.WriteLine($"Number of Combinations: {result.Count()}");
        Console.ReadLine();
    }
    public static IEnumerable<string> GetSubsets(int[] set, int sum, string values)
    {
        for (var i = 0; i < set.Length; i++)
        {
            var left = sum - set[i];
            var vals = values != "" ? $"{set[i]} + {values}" : $"{set[i]}";
            if (left == 0) yield return vals;
            else
            {
                int[] possible = set.Take(i).Where(n => n <= sum).ToArray();
                if (possible.Length <= 0) continue;
                foreach (string s in GetSubsets(possible, left, vals)) yield return s;
            }
        }
    }

4. 使用二叉搜索。线性时间。

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };
        var subsets = GetSubsets(numbers, target);
        foreach (var s in subsets) Console.WriteLine($"{s} = {target}");
        Console.WriteLine($"Number of Combinations: {subsets.Count()}");
        Console.ReadKey();
    }

    private static IEnumerable<string> GetSubsets(int[] array, int target)
    {      
        Array.Sort((Array)array);
        List<string> result = new List<string>();
        for (int i = array.Length-1; i >= 0; i--)
        {
            var eq = $"{array[i]}";
            var sum = array[i];
            var toAdd = 0;
            while (sum != target)
            {
                var mid = Array.BinarySearch(array, 0, sum <= target / 2 && sum != array[i] ? array.Length - 1 : i, target - sum);
                mid = mid < 0 ? ~mid - 1 : mid;
                if (mid == i  || mid < 0 || toAdd == array[mid] ) break;
                toAdd = array[mid];
                sum += array[mid];
                eq += $" + {array[mid]}";
                if (sum == target) result.Add(eq);
            }
        }
        return result;
    }

使用递归。请注意，此解决方案将优先选择可以使用列表中的第一项获取的解决方案。因此，对于20的目标，您不会得到12+8作为解决方案，而是5+7+8。

List<int> findSum(List<int> numbers, int target, int index = 0)
{
    // loop through all numbers starting from the index
    for (var i = index; i < numbers.Count; i++)
    {
        int remainder = target - numbers[i];
        // if the current number is too big for the target, skip
        if (remainder < 0)
            continue;
        // if the current number is a solution, return a list with it
        else if (remainder == 0)
            return new List<int>() { numbers[i] };
        else
        {
            // otherwise try to find a sum for the remainder later in the list
            var s = findSum(numbers, remainder, i + 1);
            // if no number was returned, we could’t find a solution, so skip
            if (s.Count == 0)
                continue;
            // otherwise we found a solution, so add our current number to it
            // and return the result
            s.Insert(0, numbers[i]);
            return s;
        }
    }
    // if we end up here, we checked all the numbers in the list and
    // found no solution
    return new List<int>();
}
void Main()
{
    List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };
    Console.WriteLine(findSum(myList, 12)); // 5, 7
    Console.WriteLine(findSum(myList, 20)); // 5, 7, 8
    Console.WriteLine(findSum(myList, 31)); // 5, 7, 12, 7
}

我在 C# 中的这个实现将返回等于给定数字的所有组合（包括重复使用相同的数字）。

string r;
List<int> l = new List<int>();
void u(int w, int s, int K, int[] A) { 
    // If a unique combination is found 
    if (s == K) { 
        r += "(" + String.Join(" ", l) + ")";
        return; 
    } 
    // For all other combinations
    for (int i=w; i<A.Length; i++){
        // Check if the sum exceeds K 
        int x = A[i];
        if (s + x <= K){
            l.Add(x);
            u(i, s + x, K,A);
            l.Remove(x);
        }
    }
} 
string combinationSum(int[] a, int s) {
    r = "";
    u(0, 0, s, a.Distinct().OrderBy(x=>x).ToArray());
    return r.Any() ? r : "Empty";
}

对于 a：[2， 3， 5， 9] 和 s = 9

结果将是："（2 2 2 3）（2 2 5）（3 3 3）（9）"

相关文章：