日期:2014-05-18  浏览次数:20679 次

100分求个算法,语言不限 先到先得
本帖最后由 T18LiQing 于 2013-04-02 13:28:13 编辑
一堆任意数字如:1,3,4,5,8,7,8,10,34
找到相加结果位25的这组数:
如:7+8+10=25
    1+4+5+7+8=25

这个结果集。

纠结了,请各位帮忙
算法

------解决方案--------------------
接分了。。。

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

/**
 * java 代码实现组合的算法 从n个数里取出m个数的组合是n*(n-1)*...*(n-m+1)/m*(m-1)*...2*1
 * 
 * @author dubensong
 * 
 */
public class AssemblyDemo {
/**
 * @param a:组合数组
 * @param m:生成组合长度
 * @return :所有可能的组合数组列表
 */
private List<int[]> combination(int[] a, int m) {
AssemblyDemo c = new AssemblyDemo();
List<int[]> list = new ArrayList<int[]>();
int n = a.length;
boolean end = false; // 是否是最后一种组合的标记
// 生成辅助数组。首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
int[] tempNum = new int[n];
for (int i = 0; i < n; i++) {
if (i < m) {
tempNum[i] = 1;

} else {
tempNum[i] = 0;
}
}
list.add(c.createResult(a, tempNum, m));// 打印第一种默认组合
int k = 0;// 标记位
while (!end) {
boolean findFirst = false;
boolean swap = false;
// 然后从左到右扫描数组元素值的"10"组合,找到第一个"10"组合后将其变为"01"
for (int i = 0; i < n; i++) {
int l = 0;
if (!findFirst && tempNum[i] == 1) {
k = i;
findFirst = true;
}
if (tempNum[i] == 1 && tempNum[i + 1] == 0) {
tempNum[i] = 0;
tempNum[i + 1] = 1;
swap = true;
for (l = 0; l < i - k; l++) { // 同时将其左边的所有"1"全部移动到数组的最左端。
tempNum[l] = tempNum[k + l];
}
for (l = i - k; l < i; l++) {
tempNum[l] = 0;
}
if (k == i && i + 1 == n - m) {// 假如第一个"1"刚刚移动到第n-m+1个位置,则终止整个寻找
end = true;
}
}
if (swap) {
break;
}
}
list.add(c.createResult(a, tempNum, m));// 添加下一种默认组合
}
return list;
}

public int[] createResult(int[] a, int[] temp, int m) {
int[] result = new int[m];
int j = 0;
for (int i = 0; i < a.length; i++) {
if (temp[i] == 1) {
result[j] = a[i];
j++;
}
}
return result;
}

public void print(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "\t");
}
System.out.println();
}

public void printRes