01背包问题，动态规划

/*
w代表物品重量，v代表物品价值，c代表背包最大能容纳重量
res[i][j]代表背包可以选择前i个物品，最大容量为j时候的最大价值

			  res[i-1][j]   									if(w[i-1] > j)
res[i][j]  = 
			  max((res[i-1][j-w[i-1]]+v[i-1]), res[i-1][j])     else
**/
public class Package01
{
	public int[][] getMaxValue(int[] w, int[] v, int c)
	{
		int n = w.length;
		int[][] res = new int[n+1][c+1];
		
		for(int i = 0; i < n+1; i ++)
		{
			res[i][0] = 0;
		}
		for(int j = 0; j < c+1; j ++)
		{
			res[0][j] = 0;
		}
		
		for(int i = 1; i < n+1; i ++)
		{
			for(int j = 1; j < c+1; j++)
			{
				if(w[i-1] > j)
				{
					res[i][j] = res[i-1][j];
				}
				else
				{
					res[i][j] = Math.max((res[i-1][j-w[i-1]]+v[i-1]), res[i-1][j]);
				}
			}
		}
		
		return res;
	}
	//反向找出选出的背包
	public int[] select(int[][] res, int[] w, int c)
	{
		int n = w.length;
		int[] x = new int[n];
		int j = c;
		for(int i = n; i > 0; i --)
		{
			if(res[i][c] > res[i-1][j])
			{
				x[i-1] = 1;
				j -= w[i-1];
			}
		}
		return x;
	}
	
	public static void main(String[] args)
	{
		int[] w = {2,3,4,5};
		int[] v = {3,4,5,7};
		int c = 10;
		Package01 p = new Package01();
		int[][] res = p.getMaxValue(w, v, c);
		int[] x = p.select(res, w, c);
		for (int i : x) 
		{
			System.out.print(i + " ");
		}
	}
}