关于背包算法由递归转迭代实现
背包算法应用很广泛，也是经典算法了，最近由于项目需要，使用了此算法。
查找到以下博客： http://puffsun.iteye.com/blog/1286331
这个写的简单易懂，估计大家一看就明白了，使用了递归算法，开始余量等于总数，容易每次循环，进行操作，直到余量等于0为止，但是还有个小Bug，打印的时候，中间有大于的时候需要跳过的，当然，他只求是否有解，我是需要答案，也不算是Bug吧。
原算法如下：
* @author Sun Kui */ public class Knapsack { public static void main(final String... args) { int[] arr = new int[5]; arr[0] = 11; arr[1] = 8; arr[2] = 7; arr[3] = 5; arr[4] = 3; Knapsack k = new Knapsack(); System.out.println(k.knapsack(arr, 0, 20, 20)); } /** *@param arr all of items in knapsack *@param start the start item to be put into the knapsack *@param left the remaining capacity of knapsack *@param sum capacity of knapsack */ public boolean knapsack(int[] arr, int start, int left, int sum) { if (arr.length == 0) { return false; } // start from the next item in original array if (start == arr.length) { int[] tempArr = new int[arr.length - 1]; for (int i = 0; i < tempArr.length; i++) { tempArr[i] = arr[i + 1]; } return knapsack(tempArr, 0, sum, sum); } else if (arr[start] > left) { return knapsack(arr, start + 1, left, sum); } else if (arr[start] == left) { for (int i = 0; i < start + 1; i++) { // print the answer out System.out.print(arr[i] + "\t"); } System.out.println(); return true; } else { return knapsack(arr, start + 1, left - arr[start], sum); } } } ?
?
我修改后如下，?
?
public class Knapsack {public static void main(final String... args) {//int a=5000;//int[] arr = new int[a];//for(int i=0;i<a;i++){//arr[i]=1;//}//Knapsack k = new Knapsack();//k.knapsack(arr, 0, a, a);//System.out.println(k.knapsack(arr, 0, a, a));int[] arr = new int[5];arr[0]=11;arr[1]=5;arr[2]=5;arr[3]=3;arr[4]=1;Knapsack k = new Knapsack();k.knapsack(arr, 0, 20, 20);System.out.println(k.knapsack(arr, 0, 20, 20));}/** * @param arr * all of items in knapsack * @param start * the start item to be put into the knapsack * @param left * the remaining capacity of knapsack * @param sum * capacity of knapsack */public boolean knapsack(int[] arr, int start, int left, int sum) {if(start%500==0){System.gc();}if (arr.length == 0) {return false;}// start from the next item in original arrayif (start == arr.length) {int[] tempArr = new int[arr.length - 1];for (int i = 0; i < tempArr.length; i++) {tempArr[i] = arr[i + 1];}return knapsack(tempArr, 0, sum, sum);} else if (arr[start] > left) {arr[start]=0;return knapsack(arr, start + 1, left, sum);} else if (arr[start] == left) {for (int i = 0; i < start + 1; i++) {// print the answer outSystem.out.print(arr[i] + "\t");}System.out.println();return true;} else {return knapsack(arr, start + 1, left - arr[start], sum);}}}?
请查看注释，如果我有超过5千的数据量需要使用此算法，则会抛出异常：StackOverflowError
当然，网上有调用gc的，有调JVM内存大小的，但这都不能解决问题，无意中，我看到一句话：
所有递归都是可以用迭代实现的
?
我就感觉有救了，今天被这个事情折腾的，数据都做不下去了，谢谢这位仁兄，我用迭代实现了如下，不知道有没有Bug，不过没时间测试了，先搞上去吧，2单数据已经无法做了。
?
import java.util.ArrayList;/** * @author xy792 */public class CopyOfKnapsack {public static void main(final String... args) {//int a = 100000;//int[] arr = new int[a];//for (int i = 0; i < a; i++) {//arr[i] = 1;//}int[] arr = new int[5];arr[0]=12;arr[1]=11;arr[2]=5;arr[3]=2;arr[4]=2;CopyOfKnapsack k = new CopyOfKnapsack(); System.out.println(k.knapsack(arr, 0, 20, 20));}/** * @param arr * all of items in knapsack * @param start * the start item to be put into the knapsack * @param left * the remaining capacity of knapsack * @param sum * capacity of knapsack */public ArrayList<Integer> knapsack(int[] arr, int start, int left, int sum) {ArrayList<Integer> list = new ArrayList<Integer>();if (arr.length == 0) {return list;}int end = arr.length + 1;while (start < end) {if (start == arr.length) {start = 0;int[] tempArr = new int[arr.length - 1];for (int i = 0; i < tempArr.length; i++) {tempArr[i] = arr[i + 1];}arr = tempArr;end=tempArr.length;left=sum;continue;}if (arr[start] > left) {//arr[start] = 0;start++;} else if (arr[start] == left) {for (int i = 0; i < start + 1; i++) {//System.out.print(arr[i] + "\t");if (arr[i] != 0) {list.add(arr[i]);}}return list;} else {left = left - arr[start];start++;}}return list;}}?
?
?
如有建议，或者Bug，可以留言。
end
??????
?