一、0-1背包问题描述：

已知:小偷在店里偷东西，小偷只带了一个最大承重为W的背包，商店里有N件商品，第i件商品的重量是weight[i]，价钱是value[i]。

限制:每种商品只有一件，可以选择拿或者不拿，不能分割，不能只拿一件商品的一部分（所以叫做0-1，0即不拿，1则整个拿走，且一种商品有且只有一件可供拿走）

问题:在不超过背包最大承重的情况下，最多能拿走多少钱的商品。

    算导上与0-1背包问题对应的是分数背包问题，分数背包问题中的物品是可以取一部分的，就是说可以拆分的，不像0-1背包中，要么全部拿走，要么不拿。分数背包问题可以用贪心算法来解，而0-1背包问题要用动态规划，原因在于0-1背包问题必须考虑背包的空余空间。

    还有一种叫做完全背包问题，完全背包问题跟这里不一样的是，每种商品有多件~~

        anyway，先来看看怎么解决0-1背包的问题。

       二、解决方案

        状态转移方程：

        假如对于i件商品和最大承重w的背包而言，最大收益为value_of_all[i][w]，其实value_of_all[i][w]的关键在于拿不拿这第i件商品。

①如果拿，则肯定要算上这第i件商品的价钱，然后再加上用w-weight[i]承重的背包去拿另外i-1件物品的最大收益；

②如果不拿，则value_of_all[i][w]=value_of_all[i-1][w]，因为这时候相当于用w承重的背包去取i-1件商品。

所以比较容易给出状态转移方程：

                                value_of_all[i][w] = MAX{value_of_all[i-1][W-weight[i]]+value[i] , value_of_all[i-1][W]}

        然后来考虑边界条件，对于第i件商品，如果weight[i]>W，则肯定是装不下的，这时value_of_all[i][w]=value_of_all[i-1][w]，因为这时第i件商品必然装不下，否则，就要参照上面的状态转移方程来计算。要注意的是对于总收益value_of_all[i][w]而言，无论是i=0或是w=0时，值都为0。

        有了上面的分析之后，就不难给出代码：

/*
 * 01背包问题，只能用动态规划来解：
 *
 * 最优子问题划分公式为：V[i,W]=MAX(V[i-1,W-Wi]+Vi , V[i-1,W]);，其中i表示包含的i种商品，W表示背包的最大承重
 *
 * Vi表示第i中商品的售价，Wi表示第i种商品的重量
 *
 * V[i,W]表示在有i种商品，背包承重最大为W的时候，能够带走的商品的价值最大值
 *
 * 上面的公式其实就是一种选择，是否要携带第i种商品，V[i-1,W-Wi]+Vi表示一定会携带第i种商品的收益，而V[i-1,W]则表示一定不带走第i种商品
 * 只带走其他i-1种商品种的一种或几种的收益。而我们的V[i,W]将在上面两个值中的最大值中取得
 *
 *
 * 我们可以比较容易的知道，当Wi>W的时候，肯定就不能带走第i件商品
 */

//商品有5件
#define N 5

//背包是重量
#define W 12

int value_of_all[N + 1][W + 1] = { 0 }; //因为要取到1~N，重量要取到1~W

//第i件商品的价格，数组中0下标的元素略去
int value[N + 1] = { 0, 6, 3, 5, 4, 6 };

//第i件商品的重量，数组中0下标的元素略去
int weight[N + 1] = { 0, 2, 2, 6, 5, 4 };

int& max(int& a, int& b) {
	return a > b ? a : b;
}

void _01_Packages() {

	for (int i = 0; i <= N; i++) {
		value_of_all[i][0] = 0;
	}

	for (int w = 0; w <= N; w++) {
		value_of_all[0][w] = 0;
	}

	/*
	 * 公式：
	 *
	 * value_of_all[i][w]=MAX{value_of_all[i-1][W-w[i]]+value[i] , value_of_all[i-1][W]}
	 */

	for (int i = 1; i <= N; i++) {

		for (int w = 1; w <= W; w++) {

			if (weight[i] > w) {
				value_of_all[i][w] = value_of_all[i - 1][w];
			} else {

				value_of_all[i][w] =
						value_of_all[i - 1][w]
								> (value_of_all[i - 1][w - weight[i]] + value[i]) ?
								value_of_all[i - 1][w] :
								(value_of_all[i - 1][w - weight[i]] + value[i]);
			}

		}

	}
	cout << "选择的商品的总价值最大为：" << value_of_all[N][W] << endl;
}

        三、逆推具体的最优解商品

        经过上面的函数之后，输出value_of_all[N][W]的值，就是当有N件商品，背包容量为W的时候，的最大收益，但是这时候我们还想知道当取得最大收益的时候，我们到底取了那几样商品呢？这时候我们再来看状态转移方程：

                                value_of_all[i][w] = MAX{value_of_all[i-1][W-weight[i]]+value[i] , value_of_all[i-1][W]}

        其实我们想知道的就是上面公式中的MAX函数中第一个参数大的时候取到的那些i值，因为这个时候就是我们将第i件商品“拿到”背包的时候。我们可以依次往前验证，看看value_of_all[i][w]是不是等于value_of_all[i - 1][w - weight[i]] + value[i]，如果是我们就把这个i值入栈，如果不是就略去；将i的值减一，然后继续上面的验证，直到i=1为止。

        然后再将上面存放i值的栈依次出栈，就可以得到从i=1到N的的过程中，依次拿了哪些商品了。

/*
 * 打印01背包问题的最佳收益的商品选择组成
 * param:
 * n代表商品的个数，w代表背包的重量
 */
void Print(stack<int>* result, int n, int w) {
	for (int i = n; i >= 1; i--) {
		if (value_of_all[i][w] > value_of_all[i - 1][w]) {
			result->push(i);
		}
	}

	cout << "选择了：";
	while (!result->empty()) {
		cout << "第" << result->top() << ' ';
		result->pop();
	}
	cout << "件商品" << endl;
}

int main() {

	_01_Packages();

	stack<int>* result = new stack<int>;

	Print(result, N, W);

	delete result;

	result = NULL;

	return 0;
}

输出结果：

【算法导论】0-1背包问题