找出集合中的数字组合加起来等于给定的总数

背包问题的这个特例叫做 Subset Sum .

C版

安装测试:

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
    // subtotal list
    List<double> totals = new List<double>(new double[] { 1, -1, 18, 23, 3.50, 8, 70, 99.50, 87, 22, 4, 4, 100.50, 120, 27, 101.50, 100.50 });

    // get matches
    List<double[]> results = Knapsack.MatchTotal(100.50, totals);

    // print results
    foreach (var result in results)
    {
        Console.WriteLine(string.Join(",", result));
    }

    Console.WriteLine("Done.");
    Console.ReadKey();
    }
}

using System.Collections.Generic;
using System.Linq;

public class Knapsack
{
    internal static List<double[]> MatchTotal(double theTotal, List<double> subTotals)
    {
    List<double[]> results = new List<double[]>();

    while (subTotals.Contains(theTotal))
    {
        results.Add(new double[1] { theTotal });
        subTotals.Remove(theTotal);
    }

    // if no subtotals were passed
    // or all matched the Total
    // return
    if (subTotals.Count == 0)
        return results;

    subTotals.Sort();

    double mostNegativeNumber = subTotals[0];
    if (mostNegativeNumber > 0)
        mostNegativeNumber = 0;

    // if there aren't any negative values
    // we can remove any values bigger than the total
    if (mostNegativeNumber == 0)
        subTotals.RemoveAll(d => d > theTotal);

    // if there aren't any negative values
    // and sum is less than the total no need to look further
    if (mostNegativeNumber == 0 && subTotals.Sum() < theTotal)
        return results;

    // get the combinations for the remaining subTotals
    // skip 1 since we already removed subTotals that match
    for (int choose = 2; choose <= subTotals.Count; choose++)
    {
        // get combinations for each length
        IEnumerable<IEnumerable<double>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose);

        // add combinations where the sum mathces the total to the result list
        results.AddRange(from combo in combos
                 where combo.Sum() == theTotal
                 select combo.ToArray());
    }

    return results;
    }
}

public static class Combination
{
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int choose)
    {
    return choose == 0 ?                        // if choose = 0
        new[] { new T[0] } :                    // return empty Type array
        elements.SelectMany((element, i) =>     // else recursively iterate over array to create combinations
        elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo)));
    }
}

结果:

100.5
100.5
-1,101.5
1,99.5
3.5,27,70
3.5,4,23,70
3.5,4,23,70
-1,1,3.5,27,70
1,3.5,4,22,70
1,3.5,4,22,70
1,3.5,8,18,70
-1,1,3.5,4,23,70
-1,1,3.5,4,23,70
1,3.5,4,4,18,70
-1,3.5,8,18,22,23,27
-1,3.5,4,4,18,22,23,27
Done.

如果小计重复,将出现重复的结果(期望的效果)。实际上,您可能希望使用带有某个ID的subTotal Tupled,以便将其与数据关联起来。

如果我正确地理解了你的问题,你有一组交易,你只想知道哪一个可以包含在一个给定的总数中。因此,如果有4个可能的事务,那么就有2^4=16个可能的集要检查。这个问题是,对于100个可能的事务,搜索空间有2^100=1267650600228229401496703205376个可能的组合要搜索。对于组合中的1000个潜在交易,它将增长到

10715086071862673209484250490600181056414011705336074437503883703510511249361224931983788156958127559467291755314682551871452856231404359845774698574803393456748242309854210746052371418779541821530474983581947376751655946077062914571196477654216760429831652624386837205668069376

必须测试的集合。暴力很难解决这些问题。

knapsack 问题。但即便如此,我也不确定你是否能在不使用暴力的情况下,生成所有可能的解决方案的完整枚举。

有一个廉价的Excel插件可以解决这个问题: SumMatch

https://superuser.com/questions/204925/excel-find-a-subset-of-numbers-that-add-to-a-given-total

其类0-1背包问题是NP完全的,可在多项式时间内通过动态规划求解。

http://en.wikipedia.org/wiki/Knapsack_problem

但是在算法的最后,你还需要检查和是你想要的。

不是一个超高效的解决方案,但这里有一个coffeescript实现

combinations 返回中元素的所有可能组合 list

combinations = (list) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if( y & permuations and (y isnt permuations))
                    out.push(list[i])

            if out.length <= list.length and out.length > 0
                combinations.push(out)

            permuations--

        return combinations

find_components 利用它来决定哪些数字加起来 total

find_components = (total, list) ->
    # given a list that is assumed to have only unique elements

        list_combinations = combinations(list)

        for combination in list_combinations
            sum = 0
            for number in combination
                sum += number

            if sum is total
                return combination
        return []

这是一个例子

list = [7.2, 3.3, 4.5, 6.0, 2, 4.1]
total = 7.2 + 2 + 4.1

console.log(find_components(total, list)) 

[ 7.2, 2, 4.1 ]