子集和算法效率

本文关键字：效率 算法 子集 | 更新日期: 2023-09-27 18:01:04

我们每天都有许多付款(Transaction(进入我们的业务。每个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;
    }
}

子集和算法效率

如前所述，您的问题可以通过伪多项式算法来解决，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

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

是的。

我目前无法提供完整的代码，但不要将每个事务列表迭代两次直到找到匹配项(O 平方(，请尝试以下概念：

  1. 设置一个哈希表，将现有交易金额作为条目，以及每组两笔交易的总和，假设每组值最多由两笔交易组成(周末信用卡处理(。
  2. 对于每个总数，引用到哈希表 - 该槽中的事务集是匹配事务的列表。

代替 O^2，您可以将其降低到 4*O，这将在速度上产生显着差异。

祝你好运！

动态规划可以有效地解决这个问题：假设您有 n 个事务，最大事务量为 m。我们可以在O(nm(的复杂性中解决它。

在背包问题中学习它。对于这个问题，我们可以为 pre i 事务定义子集的数量，加起来就是 sum：dp[i][sum]。等式：

for i 1 to n:
    dp[i][sum] = dp[i - 1][sum - amount_i]

DP[n][总和]是你需要的数字，你需要添加一些技巧来得到所有的子集。块引用

你在这里有几个实际的假设，可以使聪明的分支修剪的蛮力变得可行：

  • 项目是唯一的，因此您不会得到有效子集的组合爆炸(即(
    • 1,1,1,1,1,1,1,1,1,1,1,1,1,1(加起来为3(
  • 如果生成的可行集的数量仍然很大，则在遇到总运行时问题之前，收集它们的内存会不足。
  • 排序输入升序将允许轻松提前停止检查 - 如果您的剩余总和小于当前元素，则所有尚未检查的项目都不可能在结果中(因为当前和后续项目只会变得更大(
  • 保持运行总和会加快每一步的速度，因为您不会一遍又一遍地重新计算它

下面是一些代码：

public static List<T[]> SubsetSums<T>(T[] items, int target, Func<T, int> amountGetter)
    {
        Stack<T> unusedItems = new Stack<T>(items.OrderByDescending(amountGetter));
        Stack<T> usedItems = new Stack<T>();
        List<T[]> results = new List<T[]>();
        SubsetSumsRec(unusedItems, usedItems, target, results, amountGetter);
        return results;
    }
    public static void SubsetSumsRec<T>(Stack<T> unusedItems, Stack<T> usedItems, int targetSum, List<T[]> results, Func<T,int> amountGetter)
    {
        if (targetSum == 0)
            results.Add(usedItems.ToArray());
        if (targetSum < 0 || unusedItems.Count == 0)
            return;
        var item = unusedItems.Pop();
        int currentAmount = amountGetter(item);
        if (targetSum >= currentAmount)
        {
            // case 1: use current element
            usedItems.Push(item);
            SubsetSumsRec(unusedItems, usedItems, targetSum - currentAmount, results, amountGetter);
            usedItems.Pop();
            // case 2: skip current element
            SubsetSumsRec(unusedItems, usedItems, targetSum, results, amountGetter);
        }
        unusedItems.Push(item);
    }

我已经针对 100k 输入运行它，在 1 毫秒内产生大约 25k 的结果，因此它应该能够轻松处理您的 740 案例。

相关文章：