求排列组合算法，不同数值组合成一米的算法，高手请进

Question

需求是这样的，有100个不同的产品，每个产品有不同的宽度，如：15厘米，30厘米，35厘米，50厘米，100厘米等，现想让不同的产品进行组合，组合成长度1米的多个产品组合，怎么计算出有多少种组合，每种组合是由哪几个产品组成的，有没有大神能指点一下，或写出算法，不论是C、.NET、JAVA的都可以，谢谢了。

Answer 1

典型不可分割无限取且须放满背包问题

对于这类背包问题，通常是穷举找组合。

设一个数组num[6]，num[1]至num[5]分别是100、50、35、30、15的个数（大的排在前边），即num[1]=1时，100厘米的产品只要1个。另外为了程序运行方便，也会相应设另外一个数组value[6]，分别是各个产品的厘米数，即value[1]=100。
设了数组，然后就是穷举，具体方法是：先让value[1]的产品取满，即计算出num[1]=10，其他num[2]至num[5]都是0个；因此得出第一个组合，10,0,0,0,0。

得到第一个组合后，就减少一个value[1]，将多出来的厘米数，用value[2]来填满，即得出第二个组合，9,2,0,0,0。

得出第二个组合后，第三个组合，需要减少一个value[2]（为什么不是减少一个vlaue[1]，因为为了统计方便和程序运行方便，也方便人看出思路，组合的第一个数需要保持9不变，直至第一个数为9的组合全找出来，再找第一个数为8的组合），相应地使用value[3]来填满。
但发觉增加一个value[3]之后，还未满，再增加一个value[3]，却又超过了1米的限制。
那么就去找，增加一个value[4]，但又发觉，增加一个value[4]后，也会超过限制。
所以最后增加一个value[5]，于是第三个组合出来了，9,1,1,0,1。

9,1,1,0,1，接下来就是减少一个value[5]腾出空间，但发现已经没有更小的产品了，那么就在减少一个value[5]后，再减少一个value[3]，腾出空间
现在腾出的空间有50，刚才已经减了value[3]，那就去增加一个value[4]；增加后发现未满，增加一个value[5]；发现还没满，减一个value[5]，再减一个value[4]，接着再减一个value[2]，增加一个value[3]，继续寻求。。。

文字表达可能比较繁琐，用列举组合的方法可能比较直观。
10,0,0,0,0 要
9,2,0,0,0 要
9,1,1,0,1 要
9,1,0,1,1 不要
9,0,2,1,0 要
9,0,2,0,2 要
9,0,1,2,0 不要
9,0,1,1,2 不要
9,0,1,0,4 不要
9,0,0,3,0 不要
9,0,0,2,2 不要
9,0,0,1,4 不要
9,0,0,0,6 不要
8,4,0,0,0 要
。。。。。。

要的，都是可以刚好凑齐1米宽度的组合，不要的是没有凑齐的。
一直穷举下去，答案出来了。
用递归会比较容易实现和比较容易看明白。

Answer 2

动态规划。

追问

能说得具体些吗？

追答

动态规划有点绕， 很难在这里表述清楚。 如果你想弄明白原理 可以看一下背包九讲。
如果只是想要实现的代码 ，我可以写给你。

追问

好啊好啊，给我写段代码吧，看得明白些，谢谢大神了。