找出哪些数字在一组的组合加起来给定的总 [英] 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屋！