一、定义

0-1背包问题是动态规划的一种，具体描述如下：

有一个背包，它的容量为C（Capacity），现在有n种不同的物品编号为0……n-1，其中每一件物品的重量为w(i)[也就是该物品需要占用几个容量格子]，价值v(i)。问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最大。

暴力解法：每一件物品都尝试放进背包，也可以不放进背包。时间复杂度是O(（2^n）*n)。当然也可以转换为递归算法，进而找到其重复的计算，之后使用记忆化搜索进行优化。

二、具体解释

0-1背包问题：F（n, C）考虑将n个物品放进容量为C的背包，使得价值最大。动态转移方程如下：

F(i, C)=max(F(i-1,C), v(i) + F(i-1,C-w(i)))

该状态方程的具体含义：取不放入第i个物品，和放入第i个物品最大背包价值中的最大值。

举例如下：

物品id	0	1	2
weight(占用背包容量格子数)	1	2	3
value	6	10	12

有一个容量为5的背包，放入不同物品后的最大值，注意每个物品最多放入一次。

	背包可能的容量
物品编号	0	1	2	3	4	5
放入 0 号物品	0	6	6	6	6	6
放入 1 号物品	0	6	10	16	16	16
放入 2号物品	0	6	10	16	18	22

上面表格的具体解释如下：

0:表示当背包的容量为0时，它能装物品的最大值只能为0（什么也装不进去）。

1:表示当背包容量为1时，只能装编号为0的物品，不论此时是否存在1号和2号物品只能装入0号，因为其他物品需要的背包容量都大于1。

2:表示当背包容量为2时，若只有编号为0的物品，则只能装0号物品，若编号为1的物品也进来了，可以与0号进行组合。但是不能同时让入0号和1号物品。

3:4:5: 同理。

三、案例分享

三种方法实现0-1背包问题如下：

public class Backpack {
	// 递归实现0-1背包问题，存在重叠子问题：因为index和capacity组成的数据对存在重复计算
	private int bestValue(int[] w, int[] v, int index, int capacity) {
		if (index < 0 || capacity <= 0)
			return 0;
		// 不考虑index这个物品
		int res = bestValue(w, v, index - 1, capacity);
		// 考虑index这个物品，且剩余的背包空间能够容纳index对应的物品
		if (capacity >= w[index])
			// v[index] + bestValue(w, v, index - 1, capacity - w[index])
			// 表示考虑index索引对应的物品加上以剩余的index-1个物品所能形成的最大值
			res = Math.max(res, v[index] + bestValue(w, v, index - 1, capacity - w[index]));
		return res;
	}

	public int backpack01(int[] w, int[] v, int capacity) {
		int n = w.length;
		// 这里n也等于v.length，其中n-1标号最大物品的索引，同时也表示所有的物品都做尝试
		return bestValue(w, v, n - 1, capacity);
	}

	/*
	 * 使用记忆化搜索法对上面的递归进行优化而实现0-1背包问题，因为是物品重量和价值两个维度，故这里使用了二维数组来存放每种组合所能形成的背包最大值
	 */
	private int[][] memory;

	private int bestValue02(int[] w, int[] v, int index, int capacity) {
		if (index < 0 || capacity <= 0)
			return 0;
		if (memory[index][capacity] != -1)
			return memory[index][capacity];
		// 不考虑index这个物品
		int res = bestValue(w, v, index - 1, capacity);
		// 考虑index这个物品，且剩余的背包空间能够容纳index对应的物品
		if (capacity >= w[index])
			res = Math.max(res, v[index] + bestValue(w, v, index - 1, capacity - w[index]));
		memory[index][capacity] = res;
		return res;
	}

	public int backpack02(int[] w, int[] v, int capacity) {
		int n = w.length;
		memory = new int[n][capacity + 1];
		// 初始化
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= capacity; j++)
				memory[i][j] = -1;
		return bestValue02(w, v, n - 1, capacity);
	}

	// 动态规划实现0-1背包问题
	public int backpack03(int[] w, int[] v, int capacity) {
		int n = w.length;
		if (w.length != v.length || 0 == n)
			return 0;
		// 先从小索引计算开始
		int[][] memory = new int[n][capacity + 1];
		// 初始化二维数组memory
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= capacity; j++)
				memory[i][j] = -1;
		// 动态规划（自底向上）先从最简单的开始，我们先考虑0号物品在背包中存放的情况
		for (int col = 0; col <= capacity; col++)
			memory[0][col] = (col >= w[0] ? v[0] : 0);

		for (int row = 1; row < n; row++)
			for (int col = 0; col <= capacity; col++) {
				// 不考虑第row个物品
				memory[row][col] = memory[row - 1][col];
				// 考虑第row个物品，且剩余的背包容量可以放下第row个物品
				if (col >= w[row])
					// 取两种可能情况的最大值，row表示物品，col表示背包容积
					memory[row][col] = Math.max(memory[row][col], v[row] + memory[row - 1][col - w[row]]);
			}
		return memory[n - 1][capacity];
	}

	public static void main(String[] args) {
		int[] w = { 1, 2, 3 };
		int[] v = { 6, 10, 12 };
		int capacity = 5;
		System.out.println(new Backpack().backpack01(w, v, capacity));
		System.out.println(new Backpack().backpack02(w, v, capacity));
		System.out.println(new Backpack().backpack03(w, v, capacity));
	}
}