子集和(硬币变化)

Question

我的问题是,我需要计算整数数组的总和与一个值的W总和

让我们说:

int array[] = {1,2,3,4,5};

我的算法只是找到从1to到的所有长度组合W / minimum(array),它等于W因为最小值为1.如果每个组合的总和等于W,则检查每个组合然后递增一个计数器N.

任何其他算法来解决这个问题？应该更快:)

更新: 好的,子集问题和背包问题都很好,但我的问题是数组的组合重复元素,如下所示:

1,1,1 -> the 1st combination
1,1,2
1,1,3
1,1,4
1,1,5
1,2,2 -> this combination is 1,2,2, not 1,2,1 because we already have 1,1,2. 
1,2,3
1,2,4
1,2,5
1,3,3 -> this combination is 1,3,3, not 1,3,1 because we already have 1,1,3. 
1,3,4
.
.
1,5,5
2,2,2 -> this combination is 2,2,2, not 2,1,1 because we already have 1,1,2. 
2,2,3
2,2,4
2,2,5
2,3,3 -> this combination is 2,3,3, not 2,3,1 because we already have 1,2,3.
.
.
5,5,5 -> Last combination

这些都是{1,2,3,4,5}长度为3的组合.子集求和问题给出了另一种我不感兴趣的组合.

所以总结的组合,W比方说W = 7,

2,5
1,1,5
1,3,3
2,2,3
1,1,2,3
1,2,2,2
1,1,1,1,3
1,1,1,2,2
1,1,1,1,1,2
1,1,1,1,1,1,1

更新: 真实问题是元素的重复1,1,1需要和生成的组合的顺序并不重要,因此1,2,1与1,1,2和相同2,1,1.

Answer 1

到目前为止还没有有效的算法,并且可能永远不会(NP完全问题).

这是子集和问题的(变体).