algorithm - 总和组合表

Question

我需要一个算法来解决这个问题:

给定一组 n 个自然数 x1,x2,...,xn，一个数 S 和 k。从集合中选出的 k 个数(一个数可以选多次)的总和与总和 S。

换句话说:列出 S 和 Bounds 的所有可能组合:n<=256, x<=1000, k<=32

例如

  problem instance: {1,2,5,9,11,12,14,15}, S=30, k=3
  There are 4 possible combinations
  S=1+14+15, 2+14+14, 5+11+15, 9+9+12.   

有了这些界限，使用蛮力是不可行的，但我认为动态规划是一个很好的方法。

方案是:表t，其中t[m,v] = m个数组成的和v的组合数。

1. Initialize t[1,x(i)], for every i.   
2. Then use formula t[m,v]=Sum(t[m-1,v-x(i)], every i satisfied v-x(i)>0), 2<=m<=k.   
3. After obtaining t[k,S], I can trace back to find all the combinations.  

问题是 t[m,v] 可以通过重复的交换组合增加，例如，由于 16=15+1 和 1+15，t[2,16]=2。此外，最终结果 f[3,30] 很大，因为 1+14+15, 1+15+14, ...,2+14+14,14+2+14,...

如何摆脱对称排列？提前致谢。

Answer 1

您可以通过在选择 x 元素的方式上强加顺序来摆脱排列。使您的表成为三元组 t[m, v, n] = x1 中的 m 数字组成的总和 v 的组合数..xn。现在观察 t[m, v, n] = t[m, v, n-1] + t[m-1, v-x_n, n]。这通过仅生成与它们在 x 中出现的顺序相反的被加数来解决排列问题。例如，它会生成 15+14+1 和 14+14+2，但永远不会生成 14+15+1。

(您可能不需要填写整个表格，因此您可能应该延迟计算；事实上，您在这里可能需要一个内存的递归函数。)