找出一组数字的哪些组合加起来等于给定的总数 [英] Find out which combinations of numbers in a set add up to a given total

问题描述

我的任务是帮助一些会计师解决他们遇到的一个常见问题 - 给出交易清单和总存款，哪些交易是存款的一部分?例如，假设我有这个数字列表:

I've been tasked with helping some accountants solve a common problem they have - given a list of transactions and a total deposit, which transactions are part of the deposit? For example, say I have this list of numbers:

1.00
2.50
3.75
8.00

而且我知道我的总存款是 10.50，我可以很容易地看到它由 8.00 和 2.50 交易组成.然而，考虑到一百笔交易和数百万的存款，这很快变得更加困难.

And I know that my total deposit is 10.50, I can easily see that it's made up of the 8.00 and 2.50 transaction. However, given a hundred transactions and a deposit in the millions, it quickly becomes much more difficult.

在测试一个蛮力解决方案(这需要很长时间而不实用)时，我有两个问题:

In testing a brute force solution (which takes way too long to be practical), I had two questions:

1. 对于大约 60 个数字的列表，它似乎可以找到十几种或更多的组合来构成任何合理的总数.我期待一个单一的组合来满足我的全部需求，或者可能有几种可能性，但似乎总是有很多组合.是否有一个数学原理来描述为什么会这样? 似乎给定一个即使是中等大小的随机数集合，您也可以找到一个倍数组合，加起来几乎是您想要的任何总数.

1. With a list of about 60 numbers, it seems to find a dozen or more combinations for any total that's reasonable. I was expecting a single combination to satisfy my total, or maybe a few possibilities, but there always seem to be a ton of combinations. Is there a math principle that describes why this is? It seems that given a collection of random numbers of even a medium size, you can find a multiple combination that adds up to just about any total you want.

我为这个问题建立了一个蛮力解决方案，但它显然是 O(n!)，而且很快就会失控.除了明显的捷径(排除大于总数本身的数字)，有没有办法缩短计算时间?

I built a brute force solution for the problem, but it's clearly O(n!), and quickly grows out of control. Aside from the obvious shortcuts (exclude numbers larger than the total themselves), is there a way to shorten the time to calculate this?

有关我当前(超慢)解决方案的详细信息:

明细金额列表从大到小排序，然后递归执行以下流程:

The list of detail amounts is sorted largest to smallest, and then the following process runs recursively:

• 选择列表中的下一项，看看将它添加到您的运行总数中是否使您的总数与目标相符.如果是，则将当前链留作匹配项.如果未达到您的目标，请将其添加到您的运行总额中，将其从明细金额列表中删除，然后再次调用此流程

通过这种方式，它可以快速排除较大的数字，将列表缩减为仅需要考虑的数字.然而，它仍然是n！并且更大的列表似乎永远不会完成，所以我对我可能能够采取的任何捷径来加快速度感兴趣 - 我怀疑即使从列表中删除 1 个数字也会将计算时间减少一半.

This way it excludes the larger numbers quickly, cutting the list down to only the numbers it needs to consider. However, it's still n! and larger lists never seem to finish, so I'm interested in any shortcuts I might be able to take to speed this up - I suspect that even cutting 1 number out of the list would cut the calculation time in half.

感谢您的帮助！

推荐答案

背包问题的这种特殊情况称为 子集总和.

This special case of the Knapsack problem is called Subset Sum.

这篇关于找出一组数字的哪些组合加起来等于给定的总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！