背包问题的递归与非递归求解
背包问题是计算机科学里的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到背包中，以使背包最后达到指定的总重量。
举例来说，假设想要背包精确地承重20公斤，并且有5个可以选择放入的数据项，它们的重量依次为11公斤、8公斤、7公斤、6公斤、5公斤。
本文使用两种方法来找出合适的组合：一是利用栈的非递归方法；二是递归方法。（均用java语言实现）
1.利用栈求解背包问题
首先定义栈的类，

public class _StackX {private int maxSize;private int[] stackArray;private int top;public _StackX(int s){//构造器maxSize=s;stackArray = new int[maxSize];top = -1;}public void push(int j){//入栈stackArray[++top] = j;}public int pop(){//出栈return stackArray[top--];}         public boolean isEmpty(){//检查栈中是否有元素return (top == -1);}}

public class testbag {private static int N=20;private static int[] a={11,8,7,6,5};private static _StackX stack;public static void main(String [] args){stack=new _StackX(10);bagProblem();System.out.print("Correct Answer is: ");while(!stack.isEmpty())System.out.print(stack.pop()+" ");}public static void bagProblem(){int i=0,j;A:while(true){j=0;while(i<a.length){N-=a[i];if(N>=0){stack.push(a[i]);j=i;if(N==0)break A;}elseN+=a[i];i++;}if(!stack.isEmpty()){stack.pop();N+=a[j];}i=++j;}}}

public class BagRecursion { static int S=20; static int n=4; static int[] a={5,6,7,8,11};public static void main(String [] args){BagRecursion bag=new BagRecursion();bag.bag(S,n);}private boolean bag(int s, int n) {if(s==0)return true;if(s<0||n<0)return false;if(bag(s-a[n],n-1)){System.out.print(a[n]+" ");return true;}return bag(s,n-1);}}