c# - 子集求和算法效率

Question

我们每天都有大量付款(交易)进入我们的业务。每个 Transaction 都有一个 ID 和一个 Amount。我们需要将这些交易中的一些与特定金额相匹配。示例:

Transaction    Amount
1              100
2              200
3              300
4              400
5              500

如果我们想找到加起来为 600 的交易，您将有多个集合 (1,2,3),(2,4),(1,5)。

我发现了一种我已经采用的算法，其工作原理如下。 30 笔交易需要 15 毫秒。但交易数量平均在 740 左右，最大值接近 6000。执行此搜索的效率更高吗？

sum_up(TransactionList, remittanceValue, ref MatchedLists);

private static void sum_up(List<Transaction> transactions, decimal target, ref List<List<Transaction>> matchedLists)
{
    sum_up_recursive(transactions, target, new List<Transaction>(), ref matchedLists);
}

private static void sum_up_recursive(List<Transaction> transactions, decimal target, List<Transaction> partial, ref List<List<Transaction>> matchedLists)
{
    decimal s = 0;
    foreach (Transaction x in partial) s += x.Amount;

    if (s == target)
    {
        matchedLists.Add(partial);
    }

    if (s > target)
        return;

    for (int i = 0; i < transactions.Count; i++)
    {
        List<Transaction> remaining = new List<Transaction>();
        Transaction n = new Transaction(0, transactions[i].ID, transactions[i].Amount);
        for (int j = i + 1; j < transactions.Count; j++) remaining.Add(transactions[j]);

        List<Transaction> partial_rec = new List<Transaction>(partial);
        partial_rec.Add(new Transaction(n.MatchNumber, n.ID, n.Amount));
        sum_up_recursive(remaining, target, partial_rec, ref matchedLists);
    }
}

将 Transaction 定义为:

class Transaction
{
    public int ID;
    public decimal Amount;
    public int MatchNumber;

    public Transaction(int matchNumber, int id, decimal amount)
    {
        ID = id;
        Amount = amount;
        MatchNumber = matchNumber;
    }
}

Answer 1

如前所述，您的问题可以通过 O(n*G) 中的伪多项式算法解决，其中 n - 项目数和 G - 您的目标金额。

第一部分问题:是否有可能实现目标总和G。以下伪/python 代码解决了它(我的机器上没有 C#):

def subsum(values, target):
    reached=[False]*(target+1) # initialize as no sums reached at all
    reached[0]=True # with 0 elements we can only achieve the sum=0
    for val in values:
        for s in reversed(xrange(target+1)): #for target, target-1,...,0
            if reached[s] and s+val<=target: # if subsum=s can be reached, that we can add the current value to this sum and build an new sum 
                reached[s+val]=True
    return reached[target] 

这个想法是什么？让我们考虑值 [1,2,3,6] 和目标总和 7:

1. 我们从一个空集开始 - 可能的总和显然是 0。
2. 现在我们看第一个元素 1 并且必须选择接受或不接受。剩下可能的总和 {0,1}。
3. 现在查看下一个元素 2:导致可能的集合 {0,1}(不采用)+{2,3}(服用)。
4. 到现在为止与您的方法没有太大区别，但现在对于元素 3 我们有可能的集合 a. 不采用 {0,1,2, 3} 和 b. 用于获取 {3,4,5,6} 导致 {0,1,2,3,4, 5,6} 作为可能的总和。您的方法的不同之处在于，有两种方法可以到达 3 并且您的递归将从那里开始两次(这不是必需的)。一遍又一遍地计算基本相同的员工是您的方法的问题，也是所提出的算法更好的原因。
   1. 作为最后一步，我们考虑 6 并得到 {0,1,2,3,4,5,6,7} 作为可能的总和。

但是您还需要导致目标总和的子集，为此我们只需要记住采用哪个元素来实现当前子总和。此版本返回一个子集，该子集导致目标总和或 None 否则:

def subsum(values, target):
    reached=[False]*(target+1)
    val_ids=[-1]*(target+1)
    reached[0]=True # with 0 elements we can only achieve the sum=0

    for (val_id,val) in enumerate(values):
        for s in reversed(xrange(target+1)): #for target, target-1,...,0
            if reached[s] and s+val<=target:
                reached[s+val]=True
                val_ids[s+val]=val_id          

    #reconstruct the subset for target:
    if not reached[target]:
        return None # means not possible
    else:
        result=[]
        current=target
        while current!=0:# search backwards jumping from predecessor to predecessor
           val_id=val_ids[current]
           result.append(val_id)
           current-=values[val_id]
        return result

作为另一种方法，您可以使用 memoization加快您当前的解决方案，记住状态 (subsum, number_of_elements_not considered) 是否有可能实现目标总和。但我会说标准动态规划在这里不太容易出错。