难题，请教高手

Question

1到19的数字 任选几个数让这几个数的和为20
列出所有的可能
ps：数字不能重复 1 + 1 + 18 是不合法的
1 + 19 和 19 + 1 记为一种情况

Answer 1

public class T {
public static void main(String[] args) {
split(20, 0);
} static LinkedList<Integer> list = new LinkedList<Integer>(); public static void split(int n, int base) {
if (n == 0) {
System.out.println(list);
return;
}
for (int i = base + 1; i <= n; i++) {
list.addLast(i);
split(n - i, i);
list.removeLast(); 
}
}}

Answer 2

典型的子集和问题
public class SubSum { // 计算
public static void compute(int[] data, int sum) {
boolean[] state = new boolean[data.length];
int p = 0;
int temp = 0;
int count = 0; while (true) {
// 累加开始
while (p != data.length) {
if (!state[p]) {
state[p] = true;
temp += data[p];
if (temp == sum) {
count++;
print(data, sum, state);
}
if (temp > sum) {
state[p] = false;
temp -= data[p];
}
}
p++;
}
// 累加结束 // 回溯开始
while (state[p - 1]) {
state[p - 1] = false;
temp -= data[p - 1];
p--;
if (p == 0) {
System.out.println(count + "种方法");
return;
}
} while (!state[p - 1]) {
p--;
if (p == 0) {
System.out.println(count + "种方法");
return;
}
} state[p - 1] = false;
temp -= data[p - 1];
// 回溯结束
}
} // 格式 化打印
public static void print(int[] data, int sum, boolean[] state) {
StringBuffer s = new StringBuffer();
for (int i = 0; i < data.length; i++) {
if (state[i]) {
s.append(data[i]);
s.append("+");
}
}
System.out.println(s.substring(0, s.length() - 1) + "=" + sum);
} public static void main(String[] args) {
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19 };
compute(data, 20);
}
}

Answer 3

当然是背包问题，你自己google下吧。。
你那代码 只能说 一般

Answer 4

“背包问题”的算法 收藏 
问题基本描述：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1,w2,...wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。

Answer 5

amdgaming的算法很漂亮，而且是经典的解法，有什么好争的？tophot和haojia0716到底有没有认真看他的算法？效率问题你好好算算他的时间复杂度吧~haojia0716的算法，太长，我承认我没看，太晚了，困但是你的算法，基本是肯定输的（推测）~

Answer 6

4L 跟 6L的运算时间差不多 4L有64种方法，6L有63种方法
关键是4L多了20，自身应该不算的吧？

Answer 7

我发现csdn里很多人真是搞笑 没研究过别人的算法就敢肯定你怎么知道我没算过？ 你算过？搞得老子对csdn失去兴趣

Answer 8

两个人的算法都不错啊.没有争的必要。一、这个问题不是背包问题，如10楼的解释。
二、背包问题的解法可根据不同的问题采用贪心法和动态规划法两种。当物品可以分割时，用贪心，当物品不可分割时用DP。
三、4楼的算法，是把20分割为互不相同的自然数，虽然是递归，但效率应该比6楼的穷举算法高。
四、6楼的求子集和的算法适用性比4楼的算法广的多，所给的集合中的数不必连续，可以任意。
五、对本题而言，4楼的算法有一个小BUG,结果中多出一个20.个人意见。

Answer 9

虽然我是局外人不想淌这浑水，但是确实有点无语，我没说6#错了，说4#的速度快，也是加了推测，错了也很可能。但是4#真的是经典解法。请大家去Google一下一下这段文字：“有一个背包，能盛放的物品总重量为S，设有N件物品”敲回车看看。这不是新题目了，第一页就能找到两次命题：腾讯2009年重庆笔试附加题、请教2002年高程的下午C语言题。
基本上递归解法都是给出来的，这个太容易想到了
而且递归解法也不一定需要连续的数，不存在可用范围问题。4#只是看了这题目的特点，没用数组而已。一道这么简单的题，争什么阿？？？？

Answer 10

注: 以下测试 我都是把打印的部分注了的(不计打印时间)
你们跑出来看看
首先是我写的 执行时间大概为387200纳秒public class SubSum { // 计算
public static void compute(int[] data, int sum) {
boolean[] state = new boolean[data.length];
int p = 0;
int temp = 0;
int count = 0; while (true) {
// 累加开始
while (p != data.length) {
if (!state[p]) {
state[p] = true;
temp += data[p];
if (temp == sum) {
count++;
// print(data, sum, state);
}
if (temp > sum) {
state[p] = false;
temp -= data[p];
}
}
p++;
}
// 累加结束 // 回溯开始
while (state[p - 1]) {
state[p - 1] = false;
temp -= data[p - 1];
p--;
if (p == 0) {
// System.out.println(count + "种方法");
return;
}
} while (!state[p - 1]) {
p--;
if (p == 0) {
// System.out.println(count + "种方法");
return;
}
} state[p - 1] = false;
temp -= data[p - 1];
// 回溯结束
}
} // 格式 化打印
public static void print(int[] data, int sum, boolean[] state) {
StringBuffer s = new StringBuffer();
for (int i = 0; i < data.length; i++) {
if (state[i]) {
s.append(data[i]);
s.append("+");
}
}
System.out.println(s.substring(0, s.length() - 1) + "=" + sum);
} public static void main(String[] args) {
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19 };
long t1=System.nanoTime();
compute(data, 20);
long t2=System.nanoTime();
System.out.println(t2-t1);
}
}再看你们说效率高的这个 执行时间大概为1057955纳秒public class T {
public static void main(String[] args) {
long t1 = System.nanoTime();
split(20, 0);
long t2 = System.nanoTime();
System.out.println(t2 - t1);
} static LinkedList<Integer> list = new LinkedList<Integer>(); public static void split(int n, int base) {
if (n == 0) {
// System.out.println(list);
return;
}
for (int i = base + 1; i <= n; i++) {
list.addLast(i);
split(n - i, i);
list.removeLast();
}
}
}注意!! 你们说效率高的这个 只能适应这个题 如果要改成适应任何数组 算任何数 要改成下面这种
执行时间大概为1428393纳秒
因为扩展了功能 所以执行时间比你们说效率高的那个还多public class SubSumRecursion2 {
private static Stack<Integer> stack = new Stack<Integer>(); public static void go(int[] data, int sum) {
go(data, sum, 0, 0);
} public static void go(int[] data, int sum, int p, int count) {
for (int i = p; i < data.length; i++) {
stack.push(data[i]);
count += data[i];
// if (count == sum) {
// System.out.println(stack);
// }
go(data, sum, i + 1, count);
stack.pop();
count -= data[i];
}
} public static void main(String[] args) {
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
long t1 = System.nanoTime();
go(data, 9);
long t2 = System.nanoTime();
System.out.println(t2 - t1);
}
}