求组合算法

jethung

求任意N个数字全部组合，数字为正整数，使其符合下列条件：
全部组合数字的合小于M;

如求三个数字组合使其和小于5则有：

0 0 1 ;0+0+1<5
0 0 2 ;0+0+2<5
0 0 3
0 0 4
0 1 0
0 1 1
0 1 2
0 1 3
0 2 1
0 2 2
0 3 1
0 4 0
.
.
.
.等等.


求一算法！各位高手指点一下迷津,最好效率高点~~

sjinny

还是用穷举吧……

lanche

如果你掌握贪心法应该可以很轻松地做出来。如果没有这些算法的知识也不要紧，将问题巧妙地转为n位m进制的计算，即每位数加至m即进位，外加条件为各位数和小于m而已，如果要算n位数之和，n比较大时用循环来累加就费力了，此时可一个累加器解决，只要该值小于m就打印，否则就跳过（提前进位）。
演示(n=3,m=5时)：
三位数   累加
0 0 0       0
0 0 1       1       开始增量
0 0 2       2
0 0 3       3
0 0 4       4
0 1 0       1        已累加至m，开始进位，低位清零，累加器置值为新进位的值
0 1 1       2
0 1 2       3
0 1 3       4
0 2 0       2        提前进位，低位清零，累加器置值为新进位的值
0 2 1       3
0 2 2       4
0 3 0       3        提前进位，低位清零，累加器置值为新进位的值
0 3 1       4
0 4 0       4        进位...
1 0 0       1        进位...
1 0 1       1        继续
...

由于水平有限，不能提供更好的算法，请见谅。

jethung

我原先就是用版主的方法实现的，效率比较低，由于运算时可能需要求960个频点，而且还是要求正负一起算的，有没有效率更高的算法？

ShiChao

如果要求个数的化，应该可以DP
你要全部打出来，恐怕DP比较费空间

改：刚才想错了，好像DP不了