求排列组合算法,不同数值组合成一米的算法,需求是这样的,有100个不同的产品,每个产品有不同的宽度,如：15厘米,30厘米,35厘米,50厘米,100厘米等,现想让不同的产品进行组合,组合成长度1米的

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米宽度的组合,不要的是没有凑齐的.
一直穷举下去,答案出来了.
用递归会比较容易实现和比较容易看明白.