动态规划之0-1背包问题

import java.util.Formatter;

public class KnapSack {

	static int[] weights = { 2, 2, 6, 5, 4 };
	static int[] values = { 6, 3, 5, 4, 6 };
	final static int C = 10;
	static int[] packages = new int[weights.length];

	// 根据动态规划函数，用一个（n + 1） * (C + 1) 的
	// 二维表V， V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值
	// 根据表达式把表的第0行和第0列初始化为0，然后一行一行的计算V[i][j]
	// V(i,j) = V(i - 1, j) j < wi
	// 或者 max{V(i-1,j), V(i-1,j-wi) + Vi}
	static int knapSack(int n, int[] w, int[] v) {
		int[][] Valus = new int[n + 1][C + 1];

		// 初始化 第0列即 重量为0时
		for (int i = 0; i <= n; i++) {
			Valus[i][0] = 0;
		}

		// 初始化第0行 即为0个物品
		for (int j = 0; j <= C; j++) {
			Valus[0][j] = 0;
		}

		// 计算第i行，进行第i次迭代。
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= C; j++) {
				if (j < w[i - 1]) {
					Valus[i][j] = Valus[i - 1][j];
				} else {
					Valus[i][j] = Math.max(Valus[i - 1][j], Valus[i - 1][j - w[i - 1]] + v[i - 1]);
				}
			}
		}

		// 求装入背包的物品
		int weight = C;
		for (int i = n; i > 0; i--) {
			if (Valus[i][weight] > Valus[i - 1][weight]) {
				packages[i - 1] = 1;
				weight = weight - w[i - 1];
			} else {
				packages[i - 1] = 0;
			}
		}

		Formatter formatter = new Formatter(System.out);
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= C; j++) {
				formatter.format("%-9s", Valus[i][j]);
			}
			System.out.println();
		}

		return Valus[n][C];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		knapSack(5, weights, values);

		for (int i : packages) {
			System.out.print(i);
		}
	}

}