日期:2014-05-20 浏览次数:20910 次
class test { public static void main(String[] args) { int sum=0; for(i=1;i<=10;i++ { for(j=1;j<=10;j++) { for(k=1;k<=10;k++) { .... //要有10个for循环以上 sum = i + j + k + ... ; if(sum==100) System.out.println(i+" "+j+" "+k+" "+...); } } } } }
------解决方案--------------------
如果只求一种结果,用回溯法就可以了
给个例子,只求一种解
本例子可修改求多种解,即把每次找到结果后并不退出循环,而是保存到一个List<List<Integer>>结果中,直到无法找到结果为止,这里偷懒就不做了
import java.util.*; public class Test { public static void main(String[] args) throws Throwable { List<Integer> list = getCombine(Arrays.asList(new Integer[]{2,4,5,6,7,9}), 100); if (list.size() > 0) { System.out.println(list); } else { System.out.println("no result."); } } public static List<Integer> getCombine(List<Integer> list, int sum) { List<List<Integer>> used = new ArrayList<List<Integer>>(); //记录某个位置用过的数字 List<Integer> result = new ArrayList<Integer>(); //结果 Collections.sort(list); //多个数字从小到大排列好 int index = 0; int remain = sum, last; while (remain > 0) { //剩余的和>0一直循环 index++; if (used.size() < index) {used.add(new ArrayList<Integer>());} List<Integer> valid = new ArrayList<Integer>(list); //有效数字 valid.removeAll(used.get(index-1)); //去掉某个位置使用过的数字 if (valid.size() == 0) { //如果都使用过了 if (index == 1) { break; } used.get(index-1).clear(); //当前位置使用过的数字清空 if (result.size() > 0) { last = result.remove(result.size()-1); //结果的最后一个数字去掉 remain += last; //把去掉的数字还原回原来的和 used.get(index-2).add(last); //当前位置的上一个位置追加使用过的数字 } index -= 2; continue; } last = valid.get(valid.size()-1); //获取有效数字的最大数字 //last = valid.get((int)(Math.random()*valid.size())); //随即获取有效数字 result.add(last); //获取的数字保存到结果集 remain -= last; //剩余的和 if (list.contains(remain)) { //如果剩余的和刚好也在数字集合中 result.add(remain); //则获取结果,并退出循环 break; //获取结果后可以不退出,继续寻找下一种结果,当然要做一些额外的恢复处理 } else if (remain < list.get(0)) { //如果剩余的和没法用集合的数字求和得到 remain += last; //则恢复剩余的和 result.remove(result.size()-1);//并把结果集最后的一个数组去掉 index--; used.get(index).add(last); //并在当前位置记录使用过的数字 } } return result; } }
------解决方案--------------------
贪心算法不知道可行,这个丢的时间太长,抽出总和小于100的是可以,呵呵
--signature--------------------
http://www.lunwenwa.com/
------解决方案--------------------