0-1背包问题

本文记录学习0-1背包问题时的总结，详细介绍了对背包问题的暴力解法，二维数组的思路以及滚动数组思路的理解，并给出详细注释与代码。

¶背包问题的暴力解法

​ 待选物品无非是有两种状态，选与不选。背包问题求解最大价值量的问题，可以转换成遍历所有物品的各种组合，将价值与重量的总和记录在一个变量中。重量作为遍历条件，价值总量作为输出结果的一个选择。问题就回归到了回溯算法中的组合问题。力扣中39，40，216题是组合问题的经典问题，借照这些题的解法思想，背包问题的暴力解法可如下所示:

#include <iostream>
#include <vector>

using namespace std;

class Knapsack {
public:
	int pushed_weight = 0;//已经装入的重量
	int pushed_cnt = 0;//已经装入的数量
	int pushed_value = 0;//已经装入的价值
	int max_value = -1;//记录已装入的最大价值
	//回溯整个背包的所有物品
	void backTrack(int start, vector<int> W, vector<int> V,int bag_w) {
		//start 初始遍历坐标，W记录物品重量容器,V记录物品价值容器,bag_w背包最大重量
		//当等于或超过背包上限或者所有物品都遍历完，则退出循环
		if (start>=W.size()||(pushed_cnt == W.size() || pushed_weight == bag_w)){
			if (max_value < pushed_value)
				max_value = pushed_value;
			return;
		}
		//开始回溯
		for (int i = start;i < W.size();i++) {
			if (pushed_weight + W[i] <= bag_w) {
				pushed_weight += W[i];
				pushed_value += V[i];
			}
			else continue;
			backTrack(i + 1, W, V, bag_w);
            //回溯完成后从背包中取出物品
			pushed_weight -= W[i];
			pushed_value -= V[i];
		}
	 }
	 int solving(int start, vector<int> W, vector<int> V, int bag_w) {
		 backTrack(start, W, V, bag_w);
		 return max_value;
	 }
};


int main() {
	int val;
	//创建物品容器
	vector<int> weight;//物品重量
	vector<int> value;//物品价值
	bool bag_continue = 1;
	while (bag_continue) {
		cout << "输入物品重量: ";
		while (true) {
			cin >> val;
			if (val > 0)
				weight.push_back(val);
			else
				break;
		}
		cout << "输入物品价值: ";
		for (int i = 0;i < weight.size();i++)
		{
			cin >> val;
			value.push_back(val);
		}
		cout << "输入背包重量: ";
		int bag_weight;
		cin >> bag_weight;
		Knapsack res;
		cout << res.solving(0, weight, value, bag_weight) << endl;
		weight.clear();
		value.clear();
		cout << "继续下一轮？(1/0)";
		cin >> bag_continue;
	}
}

运行结果

输入物品重量: 1 3 4 -1
输入物品价值: 15 20 30
输入背包重量: 4
35
继续下一轮？(1/0)1
输入物品重量: 3 1 3 4 -1
输入物品价值: 15 200 20 30
输入背包重量: 4
220
继续下一轮？(1/0)1
输入物品重量: 2 3 4 1 5 5
-1
输入物品价值: 2 23 22 5 3 12
输入背包重量: 14
62
继续下一轮？(1/0)0

¶二维动规数组

​ 如果采用动态规划的思路来求解背包问题，使用二维数组来记录过程值是比较好理解的一种方式。用dp[i][j]来表示这个数组，行号i 表示可取物品在0~i编号中选取，列号j 表示此时的背包容量，注意区分，此时这个背包容量与给定的背包容量是不同的。动态规划的思路是将最终目标分化为一个个小的目标来逼近，j所代表的背包容量即为求这些"小目标"时的背包容量。

​ 在理解了dp数组所表示的含有后，给出如下的代码

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int Knapsack( vector<int> goods_weight, vector<int> goods_value,int bag_weight) {
	//建立dp数组，初始化为0
	//dp数组横坐标i表示可选物品标号0-i,纵坐标j表示此刻的背包重量
	vector<vector<int> >dp(goods_weight.size() , vector<int>(bag_weight+1,0));
	//第一列为背包为0时的最大价值量，仍为0
	//第一行的初始化
	for (int j = bag_weight;j - goods_weight[0]>=0;j--) {
		dp[0][j] = goods_value[0];
	}
	//理解二维dp数组的更新可以理解成列相关的更新，每次更新新的物品是，比较腾出该物品的空间放入背包后的价值量是否增加
	for (int i = 1;i < goods_weight.size();i++) {
		for (int j = 1;j <= bag_weight;j++) {
			if (j < goods_weight[i])dp[i][j] = dp[i-1][j];//此时背包容量容不下，此点处值为上一行的值
			else
			{	//若能容下比较选择物品加入背包和不选择该物品加入背包的价值量
				dp[i][j] = max(dp[i - 1][j - goods_weight[i]] + goods_value[i], dp[i - 1][j]);
			}
		}
	}

	return dp[goods_weight.size() - 1][bag_weight];
}


int main() {
	vector<int> weight = { 1, 3, 4 };
	vector<int> value = { 15, 20, 30 };
	int bag = 4;
	cout << Knapsack(weight, value, bag);
}

运行结果

35

¶滚动数组

​ 在写二维动态数组的时候，能明显感受到一个点处与上一个阶段的背包容量相关性很小，所以是否有一个方案，可以将二维数组压缩为一维数组？答案是有的。设dp[j]，j表示背包的不同阶段的质量，而数组值表示这一轮循环中可选物品中能组合出的最大的价值。

​ 算法的整体思路与二维数组的方案大同小异，用一层循环遍历物品，每次循环多将一个物品纳入可考量的范畴，第二层循环是比较有新的物品加入选择范畴后价值的最大量是否发生变化。

​ 有一点需要注意，第二层遍历背包容量时，不能从小到大遍历，因为每次有新的物品纳入选择范畴时都会加一下物品价值进行比较，并且dp数组质量大的是从质量小的推出来的，所以会出现物品价值重复累加的bug。拿一个例子：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

​ dp[1]=dp[0]+15;

​ dp[2]=dp[2-1]+15;

​ 本身dp[1]已经加了15了，dp[2]由dp[1]推出，所以在加了15的前提上又加了15，导致错误。

​ 但是从后往前遍历就没这个问题了，在没进行价值比较时，前方的数组值要么是初始值0，要么是上个循环产生的前i-1个物品所得出的最大价值量，不会产生重复加和的错误。

​ 另外，如果选用一维数组来解决背包问题时，必须先遍历物品在遍历背包容量，二维数组先遍历谁都可以。二维数组有充足的空间记录每个阶段的状态值；而一维数组空间有限，背包重量作为坐标充当索引后，就只能根据物品个数一层层向上迭代。

​ 给出的代码打印出滚动数组的更新过程

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int Knapsack( vector<int> goods_weight, vector<int> goods_value,int bag_weight) {
	//建立dp数组，初始化为0
	int goods_size = goods_value.size();//goods_size表示物品数量
	vector<int>dp(bag_weight+1,0);
	//先物品遍历
	for (int i = 0;i < goods_size;i++) {
		cout << "第" << i + 1 << "轮遍历: ";
		for (int j = bag_weight;j >= goods_weight[i];j--) {
			dp[j] = max(dp[j], dp[j - goods_weight[i]] + goods_value[i]);//加入新物品与不加新物品价值量的比较
			cout << "d["<<j<<"] = " << dp[j] << " ";//输出数组迭代过程
		}
		cout << endl;
	}
	return dp[bag_weight];
}


int main() {
	vector<int> weight = { 1,3,4,7 };
	vector<int> value = { 20, 15, 30 ,45};
	int bag = 10;
	cout << Knapsack(weight, value, bag);
}

运行结果

第1轮遍历: d[10] = 20 d[9] = 20 d[8] = 20 d[7] = 20 d[6] = 20 d[5] = 20 d[4] = 20 d[3] = 20 d[2] = 20 d[1] = 20
第2轮遍历: d[10] = 35 d[9] = 35 d[8] = 35 d[7] = 35 d[6] = 35 d[5] = 35 d[4] = 35 d[3] = 20
第3轮遍历: d[10] = 65 d[9] = 65 d[8] = 65 d[7] = 50 d[6] = 50 d[5] = 50 d[4] = 35
第4轮遍历: d[10] = 65 d[9] = 65 d[8] = 65 d[7] = 50
65