如何确定是否一组值的总和的任意组合是等于一定值？ [英] How do I determine if any combination of the sum of a set of values is equal to a certain value?

问题描述

我有一组下面的值。我需要找出的是，如果这些价值的总和的任意组合（在这种情况下，46,134.77）有一定的价值。什么是摸不着头脑的最好方法是什么？当然，它会需要几个小时才能手工完成。

和我需要知道什么组合是，如果它返回真。我可以设置这在Excel VBA中，或C＃应用程序。无论是可行的。我只是不知道如何到那里。

 125.00
 1,000.00
 1,039.36
 1,171.60
 1,200.00
 1,320.00
 1,680.00
 1,757.20
 1,768.80
 1,970.00
 2,231.25
 2,300.00
 2,369.25
 2,589.20
 2,720.00
 2,887.50
 3,000.00
 3,085.00
 3,142.60
 3,174.40
 3,742.70
 3,847.20
 5,609.25
 5,881.05
 12,240.48
 14,112.00
 29,318.07
 32,551.80

解决方案

这几乎是precisely有界的背包问题，在记录最充分研究的计算问题之一。本地：

• <一个href="http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number">Algorithm找哪个号码从大小为n总和另一个号码
列表

---

NP完全 意味着你就应该准备写< STRONG>巨环总结数字的每一个（或几乎所有）的组合。

我建议你不要用手这样做。几个小时是的总值（GDP）的低估。 这将需要你的整个人生。例如从28池中选择（这仅仅是14的）时，有14个数字超过4000万组合。

I have a set of values below. What I need to find out is if any combination of these value's sums a certain value (46,134.77 in this case). What is the best way to figure this out? Of course it would take hours to do it manually.

And I would need to know what the combination is if it returned true. I could set this up in Excel VBA, or a C# app. Whatever would work. I just have no clue how to get there.

 125.00 
 1,000.00 
 1,039.36 
 1,171.60 
 1,200.00 
 1,320.00 
 1,680.00 
 1,757.20 
 1,768.80 
 1,970.00 
 2,231.25 
 2,300.00 
 2,369.25 
 2,589.20 
 2,720.00 
 2,887.50 
 3,000.00 
 3,085.00 
 3,142.60 
 3,174.40 
 3,742.70 
 3,847.20 
 5,609.25 
 5,881.05 
 12,240.48 
 14,112.00 
 29,318.07 
 32,551.80 

解决方案

This is almost precisely a bounded knapsack problem, one of the most well-studied computation problems in history. Locally:

• Algorithm to find which numbers from a list of size n sum to another number

---

NP Complete means you should get ready to write a giant loop summing up every (or nearly every) combination of numbers.

I'd recommend not doing this by hand. Several hours is a gross underestimation. It would take your whole life. For example there are over 40 million combinations of 14 numbers when choosing from a pool of 28. (That's just the 14's).

这篇关于如何确定是否一组值的总和的任意组合是等于一定值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！