# 题目

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight [i]，得到的价值是 value [i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

# 分析

# 二维 dp 数组 01 背包

1 确定 dp 数组以及下标含义

对于背包问题，有一种写法，是使用二维数组，即 dp【i】【j】表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

2 确定递推公式

dp [i] [j] 有两种情况

第一种 不放物品 i：由 dp [i - 1] [j] 推出，即背包容量为 j，里面不放物品 i 的最大价值，此时 dp [i][j] 就是 dp [i - 1] [j]。(其实就是当物品 i 的重量大于背包 j 的重量时，物品 i 无法放进背包中，所以背包内的价值依然和前面相同。

第二种 放物品 i：由 dp [i - 1] [j - weight [i]] 推出，dp [i - 1] [j - weight [i]] 为背包容量为 j - weight [i] 的时候不放物品 i 的最大价值，那么 dp [i - 1][j - weight [i]] + value [i] （物品 i 的价值），就是背包放物品 i 得到的最大价值

所以递归公式： dp [i][j] = max (dp [i - 1] [j], dp [i - 1] [j - weight [i]] + value [i]);

3 dp 数组如何初始化

	// 初始化 dp
	vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
	for (int j = weight[0]; j <= bagweight; j++) {
	dp[0][j] = value[0];
	}

4 确定遍历顺序

先遍历物品或者背包重量都可以先遍历物品更好理解

	//weight 数组的大小就是物品个数
	for(int i = 1; i < weight.size(); i++) { // 遍历物品
	for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
	if (j < weight[i]) dp[i][j] = dp[i - 1][j];
	else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

	}
	}

5 举例

。。

完整代码

	void test_2_wei_bag_problem1() {
	vector<int> weight = {1, 3, 4};
	vector<int> value = {15, 20, 30};
	int bagweight = 4;

	// 二维数组
	vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

	// 初始化
	for (int j = weight[0]; j <= bagweight; j++) {
	dp[0][j] = value[0];
	}

	//weight 数组的大小就是物品个数
	for(int i = 1; i < weight.size(); i++) { // 遍历物品
	for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
	if (j < weight[i]) dp[i][j] = dp[i - 1][j];
	else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

	}
	}

	cout << dp[weight.size() - 1][bagweight] << endl;
	}

	int main() {
	test_2_wei_bag_problem1();
	}

# 一维 dp 数组（滚动数组）

1 确定 dp 数组的定义

在一维 dp 数组中，dp [j] 表示：容量为 j 的背包，所背的物品价值可以最大为 dp [j]。

2 一维 dp 数组的递推公式

dp [j] 为容量为 j 的背包所背的最大价值，那么如何推导 dp [j] 呢？

dp [j] 可以通过 dp [j - weight [i]] 推导出来，dp [j - weight [i]] 表示容量为 j - weight [i] 的背包所背的最大价值。

dp [j - weight [i]] + value [i] 表示容量为 j - 物品 i 重量的背包加上物品 i 的价值。（也就是容量为 j 的背包，放入物品 i 了之后的价值即：dp [j]）

此时 dp [j] 有两个选择，一个是取自己 dp [j] 相当于二维 dp 数组中的 dp [i-1][j]，即不放物品 i，一个是取 dp [j - weight [i]] + value [i]，即放物品 i，指定是取最大的，毕竟是求最大价值，

所以递归公式为：dp [j] = max (dp [j], dp [j - weight [i]] + value [i]);

3 一维 dp 数组如何初始化

关于初始化，一定要和 dp 数组的定义吻合，否则到递推公式的时候就会越来越乱。

dp [j] 表示：容量为 j 的背包，所背的物品价值可以最大为 dp [j]，那么 dp [0] 就应该是 0，因为背包容量为 0 所背的物品的最大价值就是 0。

那么 dp 数组除了下标 0 的位置，初始为 0，其他下标应该初始化多少呢？

看一下递归公式：dp [j] = max (dp [j], dp [j - weight [i]] + value [i]);

dp 数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非 0 下标都初始化为 0 就可以了。

这样才能让 dp 数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

那么我假设物品价值都是大于 0 的，所以 dp 数组初始化的时候，都初始为 0 就可以了。

4 一维 dp 数组遍历顺序

	for(int i = 0; i < weight.size(); i++) { // 遍历物品
	for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
	dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

	}
	}

完整代码

	void test_1_wei_bag_problem() {
	vector<int> weight = {1, 3, 4};
	vector<int> value = {15, 20, 30};
	int bagWeight = 4;

	// 初始化
	vector<int> dp(bagWeight + 1, 0);
	for(int i = 0; i < weight.size(); i++) { // 遍历物品
	for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
	dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	}
	}
	cout << dp[bagWeight] << endl;
	}

	int main() {
	test_1_wei_bag_problem();
	}

动态规划

# 题目

# 分析

# 二维 dp 数组 01 背包

# 一维 dp 数组（滚动数组）

整数拆分

完全背包