找出一组中的数字组合加起来给定的总数

Question

我的任务是帮助一些会计师解决他们遇到的常见问题 - 给出交易清单和总存款,哪些交易是存款的一部分？例如,假设我有这个数字列表:

1.00
2.50
3.75
8.00

我知道,我的存款总额是10.50,我可以很容易地看到它弥补了中8.00和2.50交易.然而,鉴于一百笔交易和数百万美元的存款,它很快变得更加困难.

在测试蛮力解决方案(花费太长时间以实现)时,我有两个问题:

1. 有了大约60个数字的列表,它似乎找到了十几个或更多的组合,任何合理的总数.我期待一个单一的组合来满足我的总数,或者可能是一些可能性,但似乎总是有很多组合.是否有一个数学原理描述了为什么会这样？看来,即使是中等大小的随机数集合,您也可以找到多个组合,几乎可以达到您想要的总数.

2. 我为这个问题建立了一个强力解决方案,但它显然是O(n!),并且很快失控.除了明显的快捷方式(排除大于总数的快捷方式),有没有办法缩短计算时间？

我当前(超慢)解决方案的详细信息:

详细信息量列表从最大到最小排序,然后以下过程以递归方式运行:

• 获取列表中的下一个项目,看看是否将其添加到运行总计中使您的总匹配成为目标.如果是,请将当前链作为匹配项.如果未达到目标,请将其添加到运行总计中,将其从详细信息量列表中删除,然后再次调用此过程

通过这种方式,它可以快速排除较大的数字,将列表缩小到只需要考虑的数字.但是,它仍然是n!似乎永远不会完成更大的列表,所以我对我可以采取的任何快捷方式感兴趣 - 我怀疑即使从列表中删除1个数字也会将计算时间缩短一半.

谢谢你的帮助!

Answer 1

背包问题的这种特殊情况称为子集和.

Answer 2

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.

如果重复了subTotals,则会出现重复的结果(所需的效果).实际上,您可能希望使用带有一些ID的subTotal Tupled,因此您可以将其与数据相关联.