背包问题(Knapsack problem)是一种的问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。（摘自维基百科）

下面代码为0-1类型的背包。给定一个背包，容量为C，有n个物品，各物品对应重量为W[n]，物品价值为 V[n]，向量y=[0,1,0…1,0]代表物品的选法，要么是0、要么是1，为零代表选取第i个物品，为0表示不选取第i个物品。

根据上面设定，我们可以得到如下的递归式:

    当W[n]>C时，  f(n,C)=f(n-1,C);

    当W[n]<=C时，f(n，C) = max(f(n-1,C), V[n]+f(n-1, C-W[n]) );

    初始条件为：f(i, 0) = 0; f(0,i) = 0; f(0,0) = 0;（注意下面程序判断的是当f(-1,i)时为0，这是由于java数组下标为0时还是表示有物品存在。-1表示没有物品）

    根据上面的分析用递归实现的0-1背包代码如下：

public class Testpac {	/**	 * @param args	 */	int C=12;	int W[]={2,3,4,5,6};	int V[]={1,4,3,6,8};	int y[]={-1,-1,-1,-1,-1};	public static void main(String[] args) {		// TODO Auto-generated method stub		Testpac pp=new Testpac();				System.out.println(pp.f(4,12));		pp.printY();				}	public void printY(){		for(int i=0;i
    
     C)		{			y[n]=0;			return tmp1;		}		int tmp2=V[n]+f(n-1,C-W[n]);		if(tmp1>tmp2)		{			y[n]=0;			return tmp1;		}		y[n]=1;		return tmp2;		}}