如何确定一组值之和的任何组合是否等于某个值？

Question

我在下面有一组值.我需要知道的是,如果这些值的任何组合总和一定值(在这种情况下为46,134.77).想出这个的最佳方法是什么？当然手动操作需要几个小时.

如果它返回true,我需要知道组合是什么.我可以在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 

Answer 1

正如paislee的答案中已经提到的,这是背包问题的一个变种.实际上,这个特定的问题被称为子集求和问题,就像背包问题一样,它是NP完全的.

链接的维基百科页面显示了如何使用动态编程解决问题,但请注意,由于其NP完整性,如果使整数列表过大,则总是很慢/不可能解决.

以下是一些更相关的SO问题:

• 子集和问题
• 子集和算法
• 优化子集和实现