01背包问题是动态规划算法的一个经典例题：

题目：

	  在n种物品中选取若干件（每种物品只有一件只能选择一次）
	  放在空间为W的背包里，每种物品的体积为wigth[1],wigth[2],wigth[3],wigth[n]，
	  与之相对应的价值为value[1],value[2]value[3],value[n].
	  求解怎么装物品可使背包里物品总价值最大
	

package day11;
public class O1背包 {
	/*
	 * 在n种物品中选取若干件（每种物品只有一件只能选择一次）
	 * 放在空间为W的背包里，每种物品的体积为wigth[1],wigth[2],wigth[3],wigth[n]，
	 * 与之相对应的价值为value[1],value[2]value[3],value[n].
	 * 求解怎么装物品可使背包里物品总价值最大
	 */
	static int wigth[]= {0,4,3,2,1,5};//物品质量
	static int value[]= {0,1,3,6,3,1};//物品价值
	static final int NUM=5;//物品个数
	static final int W=10;//背包容量
	static int dept[][]=new int[NUM+1][W+1];
	    //标记数组（表示第 i 个物品在装入背包容量为 j 的背包时的最大价值）
	public static void main(String[] args) {//主函数
		for(int i=1;i<=NUM;i++) {//表示第i个物品
			for(int j=1;j<=W;j++) {//表示当前背包容量
				if(wigth[i]<=j) {//可以装
					dept[i][j]=max(dept[i-1][j],dept[i-1][j-wigth[i]]+value[i]);
					    //装还是不装？
				}else {//不可以装
					dept[i][j]=dept[i-1][j];//肯定不装
				}
				System.out.print(dept[i][j]+"\t");
				    //输出前i个物品 在装入背包容量为 j 的背包时 的最大价值
			}
			System.out.println();
		}
		System.out.println("最大价值："+dept[NUM][W]);
	}
	public static int max(int x,int y) {//比较装入好，还是不装入好
		return x>y?x:y;
	}
}

这个问题的主要难点就在于理解一句话：

static int dept[][]=new int[NUM+1][W+1];//标记数组（表示第 i 个物品在装入背包容量为 j 的背包时的最大价值）

如果理解了这个二维数组，那么剩下的代码就好理解了。