代码随想录训练营第四十二天|0-1背包理论基础(一)、0-1背包理论基础(二)、416分割等和子集

0-1背包理论基础(一)

文章讲解/视频链接：代码随想录

小节：本节课讲得是0-1背包的二维数组解法，dp[i][j]的含义是从物品0-i中不重复的拿出可以装进容量为j的背包的最大价值的物品，状态转移公式为，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，初始化时第一行第一列都要初始化，遍历时顺序可以颠倒，不影响状态转移公式，并且遍历顺序从小到大就可以。

0-1背包理论基础(二)

文章讲解/视频链接：代码随想录

小节：本节课讲得是0-1背包的一维数组解法，dp[j]的含义时容量为j的背包可以装的最大价值的物品，被题是由二维压缩过来的，主要使用了一个滚动数组，将dp[i -1]的值拷贝到dp[i]中，因此状态转移公式变为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，初始化时均为0，不像上一题可以随便初始化，本题的dp[j]求取要和自身进行比较，遍历时必须要先遍历物品，再遍历背包，如果颠倒的话，展现出来的就是每个背包只能装一个物品，在对背包进行遍历时必须要从大到小遍历，如果从小到大遍历，一个物品会被取多次，不符合题意。

背包理论小节：要理解两种情况背包的状态转移方程以及遍历顺序，是否可以颠倒遍历顺序，为什么一维遍历只能从前往后遍历，初始化等等问题。为了更好的理解问题，要自己画一画dp数组的打印值，尤其是一维滚动数组，画出来后就更好理解了。 

416分割等和子集

题目链接/ 文章讲解/视频链接：代码随想录

1.代码展现

//416.分割等和子集
bool canPartition(vector<int>& nums) {//step1 构建dp数组//dp[j]的含义是背包容量为j可以装下的最大物品价值//本题的背包容量是target//这里dp数组大小之所以为10001，是因为背包容量最大为10001//因为题目中数组长度最大200，每个数最大100int nSum = 0;for (int num : nums) {nSum += num;}if (nSum % 2 == 1) return false;int nTarget = nSum / 2;vector<int> dp(nTarget + 1, 0);//step2 状态转移方程//dp[j] = max(dp[j], dp[j - weights[i]] + values[i])//本题如下，质量和价值均为nums//dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])//step3 dp数组初始化//step1中已经都初始化为0，dp[0]为0，其他初始化为0是为了//在进行遍历时不影响第一次遍历时的取值//step4 开始进行遍历for (int i = 0; i < nums.size(); i++) {for (int j = nTarget; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);//step5 打印数组}}if (dp[nTarget] == nTarget) return true;return false;
}

2.本题小节

        思考：本题是背包问题的一种应用，可以计算数组和的一半target，这里就作为背包容量，而数组中的数字作为物品，物品中的价值和质量是一样的，这样就可以直接套背包问题的状态转移公式了，背包状态转移公式为dp[j] = max(dp[j], dp[j - weight(i)] + value(i))，进行改变后为 dp[j] = max(dp[j], dp[j - nums(i)] + nums(i))，在进行遍历时，先对数组长度进行遍历，在对target进行从大到小的遍历，注意j >= nums[i]，否则没有办法装下nums[i]，最后判断是否装满，也就是dp[nTarget] == nTarget时，此时只有装满了，才满足题意