背包算法应用很广泛，也是经典算法了，最近由于项目需要，使用了此算法。
查找到以下博客： 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