蓝桥杯——说好的进阶之01背包问题

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn

求出获得最大价值的方案。

注意：在本题中，所有的体积值均为整数。

static int W = 6;
	static int[] w_arr = new int[] { 3, 4, 2 };
	static int[] p_arr = new int[] { 4, 5, 3 };
	static int[][] v;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//动态规划 填表
		cal();

		System.out.println();

		//改进版 动态规划
		k();
	}


	static void k()
	{
		int[] b=new int[W+1];
		//boolean[] m=new boolean[w_arr.length];
		for(int i=0;i<w_arr.length;i++)
		{
			for(int j=W;j>=w_arr[i];j--)
			{
				//b[j]= Math.max(b[j], b[j-w_arr[i]]+p_arr[i]);
				if(b[j-w_arr[i]]+p_arr[i]>b[j])
				{
					b[j] =b[j-w_arr[i]]+p_arr[i];
				}
			}
		}
		System.out.println("最大价值："+b[W]);
		/*for(int i=0;i<m.length;i++)
		{
			if(m[i])
				System.out.print(i+" ");
		}*/
	}
	static void cal() {
		v = new int[w_arr.length + 1][W + 1];

		for (int j = 1; j < v[0].length; j++) {
			for (int i = 1; i < v.length; i++) {
				if (w_arr[i - 1] > j) {
					v[i][j] = v[i - 1][j];
				} else {
					if (v[i - 1][j - w_arr[i - 1]] + p_arr[i - 1] > v[i - 1][j]) {
						v[i][j] = v[i - 1][j - w_arr[i - 1]] + p_arr[i - 1];
					} else {
						v[i][j] = v[i - 1][j];
					}
				}
			}
		}

		for (int i[] : v) {
			for (int j : i) {
				System.out.print(j + " ");
			}
			System.out.println();
		}
		int max = v[w_arr.length][W];
		System.out.println("最大价值："+v[w_arr.length][W]);

		System.out.print("选取物品编号：");
		get_solu(W, w_arr.length);

	}

	static void get_solu(int m, int i) {
		if (i == 0 || m == 0)
			return;
		if (v[i][m] > v[i - 1][m]) {
			get_solu(m - w_arr[i - 1], i - 1);
			System.out.print(i + " ");
		} else {
			get_solu(m, i - 1);
		}
	}