0

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

给定一组 n 个自然数 x1,x2,...,xn，一个数 S 和 k。用 sum S 形成从集合中选择的 k 个数字的总和（一个数字可以选择多次）。

换一种说法：列出 S 的所有可能组合，有界：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,...

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

4

1 回答 1

2

您可以通过对选择 x 元素的方式进行排序来消除排列。使您的表格成为三重t[m, v, n]=由 中的数字v组成的总和组合m数x1..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。

（您可能不需要填写整个表格，因此您可能应该懒惰地计算；实际上，这里可能需要一个记忆递归函数。）

于 2012-10-31T04:03:17.313 回答