求个算法思路

M=X1+。。。+Xn，且Xi(i=1...n)都不大于L，M、N、L、Xi都是都是大于0的整数，M、N、L是已知，要搞个算法求X1。。。Xn所有组合
例如：
M为7，N为3，L为3，则有组合：
3 3 1
3 2 2
时间复杂度尽量少，不要是那种指数级的。。

14 个解决方案

#1

组合个数本来就是指数级的，可LZ不要那种指数级的，那就没办法了。

如果只是求组合个数，有比较快的DP方法。

#2

无能为力，只能帮顶了。

#3

组合个数是已知的N，n就是N，打错了

引用 1 楼 litaoye 的回复:

组合个数本来就是指数级的，可LZ不要那种指数级的，那就没办法了。

如果只是求组合个数，有比较快的DP方法。

#4

好像理解错了，不好意思，你说的个数是解的个数吧。。

引用 3 楼 pengderun 的回复:

组合个数是已知的N，n就是N，打错了

引用 1 楼 litaoye 的回复:
组合个数本来就是指数级的，可LZ不要那种指数级的，那就没办法了。

如果只是求组合个数，有比较快的DP方法。

#5

解的个数是指数级，因此如果求全部解，光是输出就是指数级的，
如果只是求一个解的个数，那么有可以DP的方法。

引用 4 楼 pengderun 的回复:

好像理解错了，不好意思，你说的个数是解的个数吧。。引用 3 楼 pengderun 的回复:
组合个数是已知的N，n就是N，打错了

引用 1 楼 litaoye 的回复:
组合个数本来就是指数级的，可LZ不要那种指数级的，那就没办法了。

如果只是求组合个数，有比较快的DP方法。

#6

2n个东西里挑n个的方法数有O(2^(2n))个

#7

解的个数怎么个求法？说不定可以从解个数中得到些好方法去求解。

引用 5 楼 litaoye 的回复:

解的个数是指数级，因此如果求全部解，光是输出就是指数级的，
如果只是求一个解的个数，那么有可以DP的方法。


引用 4 楼 pengderun 的回复:

好像理解错了，不好意思，你说的个数是解的个数吧。。引用 3 楼 pengderun 的回复:
组合个数是已知的N，n就是N，打错了

引用 1 楼 litaoye 的回复:
组合个数本来就是指数级的，可LZ不要那种指数级的……

#8

好像组合数生成算法变一下形就可以实现，算法复杂度稍高Q(M)

#9

static void Main(string[] args)
        {
            int m = 20;
            int n = 13;
            int l = 13;
            int [] xi = new int[n];
            if (m > n && n * l > m)
            {
                for (int i = 0; i < n; i++)
                {
                    if ((m - n) / (l - 1) > i)
                    {
                        xi[i] = l;
                    }
                    else if ((m - n) / (l - 1) == i)
                    {
                        xi[i] = (m - n) % (l - 1) + 1;
                    }
                    else
                    {
                        xi[i] = 1;
                    }
                }
                digui(ref xi);
            }
            else
            {
                Console.WriteLine("错误条件！");
            }
            Console.ReadKey();
        }
        static void digui(ref int[] xi)
        {
            for (int i = 0; i < xi.Length; i++)
            {
                Console.Write(xi[i] + " ");
            }
            Console.WriteLine();
            if (xi[0] > xi[xi.Length - 1] + 1)
            {
                for (int i = xi.Length - 2; i >= 0; i--)
                {
                    if (xi[i] > xi[xi.Length - 1] + 1)
                    {
                        for (int j = i + 1; j < xi.Length; j++)
                        {
                            if (xi[j] < xi[i] - 1)
                            {
                                xi[j]++;
                                xi[i]--;
                                digui(ref xi);
                                break;
                            }
                        }
                    }
                }
            }
        }

#10

要求所有的可能解，速度一定快不了。试试这个。

#include <stdio.h>

int m, n, l;
int *x;
int cur;
int p;

void go(int k)
{
	int i;
	//处理完了
	if(k >= n) {
		p++;
		printf("%d: ", p);
		for(i = 0; i < n; i++)
			printf("%d ", x[i]);
		printf("\n");
		return;
	}

	//最后一个
	if(k == n - 1)
	{
		x[k] = cur;
		cur -= x[k];
		go(k + 1);
		cur += x[k];
		return;
	}

	//其余的。必须保持cur>0，否则后面的无解。
	for(i = 1; i <= l && i < cur; i++)
	{
		x[k] = i;
		cur -= x[k];
		go(k + 1);
		cur += x[k];
	}
	return;
}

int main()
{
	while(1)
	{
		scanf("%d %d %d", &m, &n, &l);
		if(m == 0) break;

		x = new int[n];
		cur = m; p = 0;

		if(m >= n) {
			go(0);
			printf("total %d solutions.\n", p);
		} else {
			printf("no solution.\n");
		}

		delete x;
		m = n = l = 0;
	}
	return 0;
}

#11

如果能减少重复的组合会更好，谢谢了！

引用 9 楼 linwq_ufida 的回复:

C# code

static void Main(string[] args)
        {
            int m = 20;
            int n = 13;
            int l = 13;
            int [] xi = new int[n];
            if (m > n && ……

#12

爪哇实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
	public static void main(String[] args) {
		List<int[]> result = test(10, 3, 4);
		int size = result.size();
		if (size == 0) {
			System.out.println("No results!");
		}
		for (int i = 0; i < size; i++) {
			int[] arr = result.get(i);
			System.out.println(Arrays.toString(arr));
		}
	}

	public static List<int[]> test(int m, int n, int l) {
		List<int[]> result = new ArrayList<int[]>();
		test(m, n, l, 1, new int[n], result);
		return result;
	}

	public static void test(int m, int n, int l, int k, int[] candidate,
			List<int[]> result) {
		if (n < 1)
			return;
		if (m > n * l)
			return;
		if (n == 1) {
			candidate[candidate.length - n] = m;
			result.add(candidate);
			return;
		}
		for (int i = Math.max(k, m - (n - 1) * l); i <= m / n && i <= l; i++) {
			int[] newCandidate = candidate.clone();
			newCandidate[candidate.length - n] = i;
			test(m - i, n - 1, l, i, newCandidate, result);
		}
	}
}

#13

JAVA看不太懂。。能不能说下思路，谢谢！

引用 12 楼 zhuzeitou 的回复:

爪哇实现


Java code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List<int[]> result = te……

#14

个人水平有限，只可以想到穷举