Day43 | 1049. 最后一块石头的重量II, 494. 目标和, 474.一和零

最后一块石头的重量II

LeetCode题目：https://leetcode.cn/problems/last-stone-weight-ii/

题目中的背包理解

  可以将其中的一个子问题抽象冲背包问题，即题中要求求得最后一块儿石头的最小重量。则易得最小的情况应当是将所有石头的重量尽量均匀的分为两部分，然后相减得到的重量。因此，本题目的背包可以看做求sum/2容量下所能的得到的最大价值。（此时同样将重量等同看做价值）

背包DP思路

  按照五步进行分析，dp数组在本题目中的含义为可以取到数组中0-i个位置的数字时，容量为sum/2的背包能否装满。因此可以递推当前第i位置的j容量背包所能承载最大价值为：max(i-1位置容量背包的最大价值，i-1位置背包容量为j-第i个位置物品的容积时背包的最大价值 + 第i个位置的物品价值)。即dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);。

  最后，根据递推公式可以执行正序的遍历得到结果，最后将结果进行(sum - dp[sum/2]) - dp[sum/2]即可，即剩余的石头减去一半容量背包所能得到的最多石头重量。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {/* dp[i]代表第i个位置时候最大价值，依然按照 */int sum = 0;for (int i = 0; i < stones.size(); i++) {sum += stones[i];}vector<int> dp(sum/2 + 1,0);for (int i = 0;i < stones.size(); i++) {for (int j = sum/2 ; j >= stones[i]; j--){dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return (sum - dp[sum/2]) - dp[sum/2];}
};

目标和

LeetCode题目：https://leetcode.cn/problems/target-sum/

  目标和总的来说，可以看作是装满一个指定容量的背包有多少种方法的问题。假设加法的总和为$x$，那么减法对应的总和就是$sum-x$。所以我们要求的是 $x-(sum-x)=target$，推得$x=(target+sum)/2$

  因此，由以上推理，问题可以简化为：当可以取到x的值时，有多少种方法组成。即此时dp的容量上限为x，dp[i]意为容量为x时最多有多少种组合方法？因此可以看作一次性可以上i个台阶的上楼梯问题，所以递推公式为dp[j] += dp[j - nums[i]];同时，注意初始化的时候，当容量为0的时候一定有一种组合方法，其他则默认为0。

  最终两次循环第一轮循环物品价值，第二轮循环背包容量，代码如下：

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];}if (sum < abs(target)) return 0;if ((target + sum) % 2 == 1) return 0;int x = (target + sum)/2;vector<int> dp(x + 1, 0);dp[0] = 1;for(int i = 0; i < nums.size(); i++) {for (int j = x ; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[x];}
};

一和零

LeetCode题目：https://leetcode.cn/problems/ones-and-zeroes/

  该问题中存在二维的数组，因此可以看做是一个二维容量的背包问题。即每个物体有两个维度的重量需要在放置的时候注意（类似于老传奇里面放物品会算占的面积）。其他仍然属于01背包的最大放置问题。

  因此，由以上推理，问题可以简化为：当可以取到第x个物品时，此时dp的容量上限为i,j（二维），dp[i][j]意为二维容量分别为i和j时最多能放下多少物品？因此可以看作多算一个容量部分的01背包问题，所以递推公式为dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j]);同时，因为有max，注意初始化的时候应该为0，当容量为0，0的时候一定装不进任何物体，因此也赋值为0。

  最终两次循环第一轮循环当前物体的二维重量，第二轮循环又有两层嵌套循环背包容量，代码如下：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (string str:strs) {int x = 0, y = 0;for (int i = 0; i < str.length(); i++) {if (str[i] == '0') x++;if (str[i] == '1') y++;}for (int i = m; i >= x; i--) {for (int j = n; j>= y; j--) {dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j]);}}}return dp[m][n];}
};