23

私は、一部の会計士が抱えている一般的な問題を解決するのを支援する任務を負っています-トランザクションのリストと合計デポジットを考えると、どのトランザクションがデポジットの一部ですか？たとえば、次の番号のリストがあるとします。

1.00
2.50
3.75
8.00

そして、私は私の総預金がであることを知っています、私はそれがとトランザクション10.50で構成されていることを簡単に見ることができます。しかし、100のトランザクションと数百万の預金を考えると、それはすぐにはるかに困難になります。8.002.50

強引な解決策をテストする際に（実用的であるには時間がかかりすぎる）、2つの質問がありました。

  1. 約60の数字のリストを見ると、妥当な合計で12以上の組み合わせが見つかるようです。私は、単一の組み合わせが私の合計、またはおそらくいくつかの可能性を満たすことを期待していましたが、常にたくさんの組み合わせがあるようです。これがなぜであるかを説明する数学の原理はありますか？中程度のサイズの乱数のコレクションを考えると、必要な合計に達する複数の組み合わせを見つけることができるようです。

  2. 私はこの問題に対して力ずくの解決策を構築しましたが、それは明らかにO（n！）であり、すぐに制御不能になります。明らかなショートカット（合計よりも大きい数を除外する）とは別に、これを計算する時間を短縮する方法はありますか？

私の現在の（超低速）ソリューションの詳細：

詳細量のリストは最大から最小にソートされ、次のプロセスが再帰的に実行されます。

  • リストの次の項目を取得し、それを現在の合計に追加すると、合計が目標と一致するかどうかを確認します。含まれている場合は、現在のチェーンを一致として取っておきます。目標を下回っている場合は、現在の合計に追加し、詳細金額のリストから削除してから、このプロセスを再度呼び出します。

このようにして、より大きな数をすばやく除外し、リストを考慮する必要のある数だけに減らします。しかし、それはまだnです！より大きなリストは決して終わらないように見えるので、これをスピードアップするために取ることができるかもしれないショートカットに興味があります-リストから1つの数字を削除するだけでも、計算時間が半分になると思います。

ご協力いただきありがとうございます！

4

8 に答える 8

18

ナップザック問題のこの特殊なケースは、サブセット合計と呼ばれます。

于 2010-10-21T17:24:32.880 に答える
10

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.

小計が繰り返されると、結果が重複しているように見えます (目的の効果)。実際には、subTotal Tupled を何らかの ID とともに使用して、それをデータに関連付けることができます。

于 2011-06-27T19:08:35.287 に答える
2

この問題を解決する安価な Excel アドインがあります: SumMatch

SumMatch の動作

于 2012-12-30T02:18:33.517 に答える
2

私があなたの問題を正しく理解していれば、あなたは一連のトランザクションを持っており、そのうちのどれが特定の合計に含まれるかを知りたいだけです. したがって、4 つの可能なトランザクションがある場合、検査する可能性のあるセットは 2^4 = 16 あります。この問題は、100 の可能なトランザクションの場合、検索スペースには 2^100 = 1267650600228229401496703205376 の可能な組み合わせが検索されることです。ミックス内の潜在的なトランザクションが 1000 の場合、合計は

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

テストする必要があるセット。ブルートフォースは、これらの問題に対する実行可能な解決策とは言えません。

代わりに、ナップザックの問題を処理できるソルバーを使用してください。しかし、それでも、ブルートフォースのバリエーションなしに、考えられるすべてのソリューションの完全な列挙を生成できるかどうかはわかりません。

于 2010-10-21T17:04:48.733 に答える
1

NP完全であり、多項式時間で動的計画法によって解決できる0-1ナップザック問題のようなものです。

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

ただし、アルゴリズムの最後に、合計が希望どおりであることも確認する必要があります。

于 2010-10-21T16:46:54.590 に答える
0

データによっては、最初に各トランザクションのセント部分を調べることができます。最初の例のように、2.50 が合計の一部である必要があることがわかっています。これは、50 に追加されるゼロ以外のセント トランザクションの唯一のセットであるためです。

于 2010-10-27T18:15:40.380 に答える
0

非常に効率的なソリューションではありませんが、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 ]

于 2013-06-27T00:03:14.003 に答える