子集和算法的效率

Question

我们每天会有一些涉及 IT 技术的付款（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;
    }
}

- anothershrubery

---

我认为这是错误的网站...（http://meta.stackexchange.com/q/165519/299295） - Sinatr

列表中有很多重复的值吗？ - samgak

不，所有的值都是唯一的，我们目前正在努力缩小我们选择的列表，但这可能不会对集合产生太大影响。 - anothershrubery

@Sinatr，我认为这是正确的领域，因为我专门研究了我所拥有的算法的C#实现。 - anothershrubery

@anothershrubery，codereview - 如果您有可用的代码并希望改进它，programmers - 最佳算法（与语言无关或 c#）。如果您遇到错误（不工作的代码）或遇到问题（性能），则Stackoverflow很好。我不是在坚持，但我认为您可以使用更好的算法。另一件事是您没有解释自己的算法，但它看起来像直接的（递归迭代），这是内存高效但性能较差的算法。 - Sinatr

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，而您的递归将从那里开始两次（这是不必要的）。反复计算基本相同的内容是您方法的问题，这也是为什么建议使用该算法的原因。
   5. 最后一步考虑 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，未考虑的元素数量）是否可能实现目标和。但我认为在这里标准的动态规划是一个更少出错的选择。

- ead

Answer 2

可以。

目前我无法提供完整的代码，但请尝试这个概念：不要再迭代每个交易列表两次以查找匹配（O平方），请按照以下步骤操作：

1. 使用现有交易金额设置哈希表条目，同时假设每个值由最多两笔交易组成（周末信用卡处理），并对每组两个交易的金额求和。
2. 对于每个总额，请在哈希表中引用-该插槽中的交易集是匹配交易的列表。

通过这种方法，您可以将其从 O 平方降至 4*O，这将大大提高速度。

祝好运！

- Mike Brake

---

该值可以由超过2个交易组成。由于交易数量没有限制，因此我不认为这会起作用？ - anothershrubery

Answer 3

动态规划能够高效地解决这个问题：假设你有n个交易，最大的交易数量为m，我们可以在O(nm)的复杂度下解决它。

在背包问题中了解更多。 针对这个问题，我们可以定义前i个交易中加起来等于sum的子集数为dp[i][sum]。 方程如下：

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

dp[n][sum]是你需要的数字数量，你需要添加一些技巧来获取所有子集。

- jibancanyang

Answer 4

在这里，您有一些实际的假设，这使得使用智能分支修剪的暴力方法成为可能：

• 物品是唯一的，因此您不会得到有效子集的组合爆炸（即（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输入的测试，结果在不到25毫秒内产生了约1k个结果，因此它应该能够轻松处理你的740个案例。

- public_static_void

---

不知道问题出在哪里，但我已经运行了你的完全相同的代码大约20分钟了，仍然没有结果... - anothershrubery

出现了 OutOfMemoryException 异常。 - anothershrubery

这基本意味着你得到的结果太多了，在实际使用中也没有什么用处。一旦获得 N 个结果，你可能想要停止并使用它们。 - public_static_void

虽然这样做可以避免问题，但却违背了练习的初衷。如果我们无法获取所有结果，那么不如一无所获，因此我们不会采用该解决方案。 - anothershrubery

没错。您可以在递归方法中添加“If (results.Count > maxresults) return;”行来提前停止。 - public_static_void