0-1背包问题（二维dp数组）&416分割等和子集&0-1背包问题（一维dp滚动数组）

day42

0-1背包问题（二维dp数组）

参考视频

掌握01背包、完全背包、多重背包

416.分割等和子集1

完全背包的物品数量是无限的

背包

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

回溯

暴力回溯，时间复杂度$o(2^n)$，其中n为物品的数量。复杂度较高，需要使用动态规划来解决

动态规划

背包最大重量为4，物品如下：

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

问背包能背的物品最大价值是多少？

二维dp数组01背包（动态规划五部曲）

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

$dp[i][j]$表示从下标为$[0-i]$的物品里任意取，放进容量为$j$的背包，价值总和最大为多少

$dp[i][j]$	0	1	2	3	4
物品0
物品1
物品2

横着走就代表j，竖着走就代表i。

确定递推公式

$dp[i][j]$:从小标为[0,i]物品里任意取，放进容量为j的背包，价值总和最大为多少

从两个方面去推导$dp[i][j]$

不放物品i:$dp[i-1][j]$，也就是背包的容量为j，里面不放物品i的最大价值，此时$dp[i][j] = dp[i-1][j]$（换句话说当物品i的重量比背包重量j还要大的时候就放不进去了，因此依然和当前的相同）
放物品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]$.

综上所述：递推公式为：

 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp数组初始化

初始化一定要和dp数组定义吻合。

初始化第一行和第一列，递推公式是根据上面一行和左上角某一个值来推导出来的，这里一定注意

$dp[i][j]$	1	2	3	4
物品0	15	15	15	15
物品1
物品2

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

对于其他位置来说，初始化为任何值都可以，这里初始化为0，为了统一。

//最终的初始化代码
// 初始化 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];
}

确定遍历顺序

物品和背包重量两个遍历维度

先遍历哪一个都可以

// 先遍历物品
// 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]);

    }
}

// 先遍历背包
// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        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]);
    }
}

这里两个遍历顺序都可以是因为遍历顺序的次序不影响$dp[i][j]$公式的推导，因此两个方法都是可以的

举例推导dp数组

手动推导

动态规划-背包问题4

// 测试代码
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数组总结

二维dp的01背包：推导公式：$dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])$

重点是背包问题的初始化和遍历顺序

0-1背包问题（一维dp滚动数组）

参考视频

问题和之前的一样，背包最大重量为4，物品为：

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

问背包能背的物品的最大价值是多少？

一维dp数组（滚动数组）五部曲

背包问题状态都是可以压缩的。

二维数组的递推公式：$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);$

$dp[i-1]$可以拷贝到dp[i]上，表达式可以是：$dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);$

因此可以只用一个一维数组，只用dp[j]

$dp[i][j]$表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

dp[i]及下标的定义

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

一维dp数组的递推公式

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]）

// 相当于把二维数组中的[i]去掉了
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

一维dp数组初始化

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

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

非0下标都初始化为0就可以了，因为递推公式里面取的是max();

一维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]);
    }
}

此时遍历顺序不一样了：倒序遍历保证物品i只被放入一次。正序遍历会被放入多次。

同时遍历顺序不能颠倒。

举例推导dp数组

动态规划-背包问题9

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的背包比二维简洁的多，初始化和遍历顺序相对简单，空间复杂度也会下降

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:

	// 二维dp数组
	int getbagMaxvalue2(vector<int>& weight, vector<int>& values,int bagweight) {
		vector<vector<int>> dp(weight.size(), vector<int>(bagweight+1, 0)); //列初始化为0
		for (int j = weight[0]; j <= bagweight; j++) {		//行初始化为对应的值
			dp[0][j] = values[0];
		}

		//递推公式
		for (int i = 1; i < weight.size(); i++) {	//遍历物品
			for (int j = 0; j <= bagweight; j++) {	//遍历背包容量 背包容量从0开始
				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]] + values[i]);
				}
			}
		}

		return dp[weight.size()-1][bagweight];
	}


	// 一维dp数组
	int getbagMaxvalue1(vector<int>& weight, vector<int>& values, int bagweight) {
		vector<int> dp(bagweight + 1, 0);	//数组初始化为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]] + values[i]);
			}
		}
		return dp[bagweight];
	}
};
int main() {
	vector<int> weight = { 1,3,4 };
	vector<int> values = { 15,20,30 };
	int bagweight = 4;
	Solution solution;
	int test = solution.getbagMaxvalue2(weight, values, bagweight);
	cout << "背包能背物品的最大价值为：";
	cout << test << endl;

	return 0;
}

416.分割等和子集

题目链接：416. 分割等和子集

解题思路：参考视频

只有确定了如下四点，才能把01背包问题套到本题上来。

背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。

动态规划五部曲：

1.确定dp[j]及下标的含义,表示容量为j的背包所能背的最大价值为dp[j]，这里数组中的值是重量也是质量

2.确定递推公式：$dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])$

3.初始化：要取得最大价值，非0下标的元素初始化为0就可以了。
vector<int> dp(10001,0);	//总和不会大于20000
4.确定遍历顺序
// 开始 01背包
for(int i = 0; i < nums.size(); i++) {	//物品
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历背包
        // 背包倒序遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
5.举例推导dp数组

dp[j]的数值一定是小于等于j的。

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

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

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 时间：O(n^2)
        // 空间：O(n)
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }

        vector<int> dp(30, 0);

        if (sum % 2 == 1) return false;
        int target = sum / 2;

        //01背包
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[target] == target) return true;
        return false;

    }
};

int main() {

    Solution solution;
    vector<int> vec = { 1,5,11,5,4 };
    bool test = solution.canPartition(vec);
    cout << test << endl;

	return 0;
}

上篇96不同的二叉搜索树&343整数拆分

下篇1049最后一块石头的重量II&494目标和&474一和零&01背包总结