动态规划（1）：01背包问题

题目：

现有n个物品，重量依次为W i（使用int[] weight表示）,价值依次为 V i(使用 int[] values表示），现有一个可装重量为17的包（使用bag表示），求使背包物品价值最大化的最优解，

规划方程：f( i , bag )=Max{  ( f( i-1,bag-weight[i])+values[i] ) , f( i-1 ,bag)  }

代码示例：

/**
 * 全排列问题（深度搜索字典序）
 * 
 * @author Swing
 * 
 */
public class Main {
	// 物品重量（记得加上一个0）
	int[] weight = new int[] { 0, 3, 4, 7, 8, 9 };
	// 物品的价值
	int[] value = new int[] { 0, 4, 5, 10, 11, 13 };
	// 包的容量
	int bag = 17;
	// 规划表(初始化都为0）
	int[][] table = new int[weight.length][bag + 1];

	// 最优解（1表示该物品被放入包中，0表示没有）
	int[] result = new int[weight.length];
	int index = result.length - 1;

	public static void main(String[] args) {
		Main main = new Main();
	}

	public Main() {
		// 求出不同数量物品在不同背包容量下的最大价值
		for (int i = 1; i < weight.length; i++) {
			for (int w = 1; w <= bag; w++) {
				// 如果此时背包容量可以放下当前对应的物品
				if (w >= weight[i]) {
					table[i][w] = Math.max(table[i - 1][w - weight[i]]
							+ value[i], table[i - 1][w]);
				}
				// 否则就不放
				else
					table[i][w] = table[i - 1][w];
			}
		}

		printTable(table);
		System.out.println("\n最大价值：" + table[weight.length - 1][bag]);
		check(weight.length - 1, bag);
		System.out.println("\n物品取舍明细如下:");
		for (int i = 0; i < result.length; i++)
			System.out.print(result[i] + "\t");

	}

	// 根据位置获取实现最大价值时的取舍方案
	// （如果table[i][w]=table[i-1][w]，则说明第i个物品没被放入包中)
	public void check(int i, int w) {
		if (index > 0) {
			if (table[i][w] == table[i - 1][w]) {
				result[index--] = 0;
				check(i - 1, w);
			} else {
				result[index--] = 1;
				check(i - 1, w - weight[i]);
			}
		}
	}

	// 输出表
	public void printTable(int[][] table) {
		System.out.println("规划表:");
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				System.out.print(table[i][j] + "\t");
			}
			System.out.println();
		}
	}

}

运行结果：