学步园

只求一个组合可以采用背包问题的思路，求所有组合的话，背包问题可能就不太适用了。

这里面采用暴力搜索＋剪枝，具体是先对给定的数组进行排序，在求解的深度优先搜索过程

中，如果出现中间的求和结果大于预先给定的数，那么就不用继续搜索了（因为后面的元素都大于

等于当前的元素，不用再往后搜索了）。

以前也写过类似的程序，但只是针对具体问题的，

这里修改了下，

给出一个比较通用的代码：

public void find(int total,int []a) {<br /> if(a == null || a.length == 0) return;<br /> //排序是为了在深搜时可以进行剪枝<br /> java.util.Arrays.sort(a);<br /> final int length = a.length;<br /> int []resultArray = new int[length];<br /> for(int i=0;i<length;i++) {<br /> resultArray[i] = 0;<br /> }<br /> resultArray[0] = 1;<br /> int count = 0;<br /> // int t_count = 0;<br /> int arrayLocationIndex = 1;//标识resultArray中有多少个位置不为0<br /> int tempNumber = 1;//标志当前已经到了resultArray的哪个下标<br /> while(true) {<br /> // t_count++;if(t_count == 100) break;<br /> if(resultArray[0] == length+1) break;//循环跳出条件<br /> int temp = 0;<br /> //for循环计算当前结果<br /> // System.out.println(java.util.Arrays.toString(resultArray));<br /> for(int i=0;i<resultArray.length;i++) {<br /> if(resultArray[i] != 0) {<br /> temp += a[resultArray[i]-1];<br /> }<br /> }<br /> if(temp == total) {//得到了一个符合条件的结果<br /> count++;<br /> //打印这个结果的内容<br /> System.out.println(java.util.Arrays.toString(resultArray));<br /> for(int i=0;i<resultArray.length;i++) {<br /> if(resultArray[i] != 0) {<br /> System.out.print(a[resultArray[i]-1]+" ");<br /> }<br /> }<br /> System.out.println();<br /> if(arrayLocationIndex == 1) {<br /> //这种情况下数组中只有一个元素，那么把它加1(a中的下标)<br /> resultArray[0]++;<br /> }else {<br /> //把resultArray中最后一个不为0的置为0，同时把倒数第二个元素＋1<br /> resultArray[tempNumber] = 0;<br /> resultArray[arrayLocationIndex++]++;<br /> tempNumber = arrayLocationIndex;<br /> }<br /> }<br /> if(temp < total) {<br /> // System.out.println("temp < total arrayLocationIndex ["+arrayLocationIndex+"]tempNumber["+tempNumber+"]");<br /> // System.out.println(java.util.Arrays.toString(resultArray));<br /> if(tempNumber < length) {<br /> //继续添加下一个<br /> tempNumber++;<br /> resultArray[arrayLocationIndex] = tempNumber;<br /> arrayLocationIndex++;<br /> }else {<br /> //已经到a的最后了，回退<br /> if(resultArray[arrayLocationIndex-1] == length) break;<br /> resultArray[arrayLocationIndex-1] = 0;<br /> resultArray[arrayLocationIndex-2]++;<br /> tempNumber = arrayLocationIndex;<br /> }<br /> // System.out.println(java.util.Arrays.toString(resultArray));<br /> }<br /> if(temp > total) {<br /> // System.out.println("temp > total arrayLocationIndex ["+arrayLocationIndex+"]tempNumber["+tempNumber+"]");<br /> // System.out.println(java.util.Arrays.toString(resultArray));<br /> if(tempNumber == 1){<br /> // System.out.println("tempNumber == 1");<br /> break;<br /> }<br /> if(tempNumber == length) {<br /> //到a数组的最后了，回退<br /> resultArray[arrayLocationIndex-2]++;<br /> tempNumber = resultArray[arrayLocationIndex-2];<br /> resultArray[arrayLocationIndex-1]=0;<br /> arrayLocationIndex--;<br /> }else {<br /> //类似于temp < total分支<br /> resultArray[arrayLocationIndex-1] = 0;<br /> resultArray[arrayLocationIndex-2]++;<br /> tempNumber = resultArray[arrayLocationIndex-2];<br /> arrayLocationIndex--;<br /> }<br /> // tempNumber = resultArray[arrayLocationIndex-1]+1;<br /> // System.out.println(java.util.Arrays.toString(resultArray));<br /> }<br /> }<br /> System.out.println(count);<br /> }