这个问题是 NP 完全问题,因此除非 P=NP,否则您将不得不对输入的大小进行指数运算。现在,此类问题的妙处在于,实际上有两种解决方法,这两种方法可以将指数放在问题的不同方面。
首先,如果您的总和没有太多元素,您可以通过搜索所有组合来暴力解决此问题。此方法与集合中的元素数量成指数关系,并且在每个容器最多包含 20 个左右元素的情况下也能很好地工作。在那之后,事情会变得非常糟糕。
第二种选择是使用动态规划。与之前的方法不同,该算法在写出每个数字所需的位数方面呈指数增长。您要做的就是跟踪所有可能和的集合以及生成它们所需的最小元素数。这是对您在答案中链接到的解决方案的简单修改。
[(4000, [4000], [2000, 2000]), (6000, [2000, 4000], [565, 1435, 2000, 2000]), (2000, [2000], [2000]), (4200, [200, 4000], [528, 800, 2872]), (10200, [200, 2000, 2000, 2000, 4000], [528, 565, 800, 1435, 2000, 2000, 2872]), (8200, [200, 2000, 2000, 4000], [528, 800, 2000, 2000, 2872]), (6200, [200, 2000, 4000], [528, 800, 2000, 2872])]