我在下面有一组值。我需要找出的是这些值的任意组合是否总和为某个值(在本例中为 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
最佳答案
正如 paislee 的回答中已经提到的，这是 knapsack problem 的变体。 .事实上，这个具体问题叫做subset sum problem。 ，和背包问题一样，它是 NP 完全问题。
链接的维基百科页面显示了如何使用动态规划解决问题，但请注意，由于其 NP 完整性，如果您的整数列表太大，解决起来总是很慢/不可能。
这里有一些更相关的 SO 问题:
关于c# - 如何确定一组值的总和的任意组合是否等于某个值？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9072558/