背包算法应用很广泛，也是经典算法了，最近由于项目需要，使用了此算法。
查找到以下博客： 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 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) { 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 out System.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]=11; // arr[1]=5; // arr[2]=5; // arr[3]=3; // arr[4]=1; CopyOfKnapsack k = new CopyOfKnapsack(); System.out.println(k.knapsack(arr, 0, a, a).size()); } /** * @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; int temp = 0; while (start < end) { if (start == arr.length) { start = ++temp; int[] tempArr = new int[arr.length - 1]; for (int i = 0; i < tempArr.length; i++) { tempArr[i] = arr[i + 1]; } arr = tempArr; end--; 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
