9

私は、各セットの任意の数のアイテムの合計を含む、さまざまな基準に基づいて2つのデータセットを一致させる必要があるアプリケーションに取り組んでいます。私はこの問題を次のステートメントにまとめました。

アイテムとトランザクションのセットが与えられた場合、合計がトランザクションの最小セットの合計に等しい最小のアイテムセットを見つけます。（この投稿では無視している複雑さがいくつかありますが、今のところ、日付、説明、明確な違いなどではなく、一致する合計金額のみに関心があります。）

または、数学的に：2セットの数値が与えられた場合、合計が等しいそれぞれから最小のセットを見つけます。

私が遭遇した他の同様のSOの質問は、あなたが前もって合計を知っているか、あなたがしようとしている各セットからの量を知っていると仮定しています。

そして、これが（私が思うに）私が何をしようとしているのかを説明するテストです。

    [TestMethod]
    public void StackOverflowTest()
    {
        var seta = new[]{10, 20, 30, 40, 50};
        var setb = new[]{ 45, 45, 100, 200 };

        var result = Magic(seta, setb);


        Assert.AreEqual(new[]{40,50},result.SetA);
        Assert.AreEqual(new[] { 45, 45 }, result.SetB);
    }
    class MagicResult
    {
        public int[] SetA { get; set; }
        public int[] SetB { get; set; }

    }
    private MagicResult Magic(int[] seta, int[] setb)
    {
        throw new NotImplementedException();
    }

私はこのパスを作成するエレガントなソリューションを探していますが、そこに到達するための疑似コードや提案を受け取ります;）

4

3 に答える 3

3

強引な：

 var result = (from a in seta.Subsets()
               from b in setb.Subsets()
               where a.Count() > 0 && b.Count() > 0
               where a.Sum() == b.Sum()
               orderby a.Count() + b.Count()
               select new MagicResult { SetA = a.ToArray(), SetB = b.ToArray() }
              ).First();

EvenMoreLINQ プロジェクトの Subsets メソッドを使用します。

于 2012-10-26T23:19:36.553 に答える
2

これは、時間の動的計画法を使用して解決できますO(nW)。ここで、W は最大和のサイズです。両方のセットのナップザック問題を解いて、考えられるすべての合計を含むそれぞれの配列を生成し、使用されたアイテムの数を追跡します。次に、各配列の等しい合計を比較して、それぞれの最小値を見つけます

テストされていませんが、これがアイデアです。

arr1dp = [None]*W;  arr1dp[0] = 0;
arr2dp = [None]*W;  arr2dp[0] = 0;


# knapsack arr1
for i in range(len(arr1)):
    for cur_item in arr1:
        if (arr1dp[cur_item] is not none):
             arr1dp[cur_item+i] = min(arr1dp[cur_item]+1,arr1dp[cur_item])

# do the same for arr2
# omitted for brevity

# find the smallest match
for i in range(W):
    if arr1dp[i] is not none and arr2dp[i] is not none:
         min_val = min(min_val,arr1dp[i]+arr2dp[i])
于 2012-10-26T23:56:48.707 に答える
1

2 つのセットに共通の数値が含まれている場合、サイズ 1 の解があります。

そうでない場合は、2 つの数値のすべての合計を試してください (N-choose-two、またはN*(N-1)/2各セットに存在します)。それらを単一数および 2 数の合計のコレクションと比較します。

喜びがない場合は、3 つの数のすべての和を試して、1、2、または 3 の数の和と比較します。など、すべての合計 (サイズ N のセットに対して 2**N) が試行されるまで続きます。

解決策が見つかるとすぐに検索を停止する作業コードを次に示します。(被加数の数が同じでも合計が小さくなる可能性があります)。それはPythonにありますが、それは実質的に疑似コードです:-)

from itertools import combinations

# To allow lists of different sizes: ensure list1 is never the short one
if len(list1) < len(list2):
    list1, list2 = list2, list1

def found(val, dict1, dict2):
    print "Sum:", val
    print "Sum 1", dict1[val]
    print "Sum 2", dict2[val]

def findsum(list1, list2):
    # Each dict has sums as keys and lists of summands as values.
    # We start with length 1:
    dict1 = dict()
    dict2 = dict()

    for n in range(1, max(len(list1), len(list2))+1):
        # Check all size n sums from list1 against size < n sums in list2
        for nums in combinations(list1, n):
            s = sum(nums)
            if s in dict1:  # Is this sum new for our list?
                continue

            dict1[s] = nums
            if s in dict2:   
                found(s, dict1, dict2)
                return   # If you want to look for a smallest sum, keep going

        # If list2 is too short, nothing to do
        if len(list2) < n:
            continue

        # Check all size n sums from list2 against size <= n sums in list1
        for nums in combinations(list2, n):
            s = sum(nums)
            if s in dict2:  # Is this sum new for our list?
                continue

            dict2[s] = nums
            if s in dict1:
                found(s, dict1, dict2)
                return   # If you want to look for a smallest sum, keep going

findsum(list1, list2)

これは、最小数の比較で解を見つけるように設計されています。合計も最小にしたい場合は、各サイズ n で、すべての n 部分の合計を一度に生成し、それらを並べ替えて昇順にチェックします。

于 2012-10-26T23:19:53.213 に答える