题目链接:1049. 最后一块石头的重量 II
思路
把石头分成重量尽量相同的两堆,这样就能保证最后一块石头的重量最小。转换为01背包问题,重量和价值都是stone。
①dp数组,dp[j]表示容量为j的背包可以装的最大价值为dp[j]
②递推公式,dp[j] = max(dp[j], dp[j - stone[i]] + stone[i])
③dp数组初始化,遍历stone数组,计算总重量,取一半为dp数组大小,值为0;或者根据题目可知最大重量为30*100=30000,取一半15000即可,值为0
④遍历顺序,一维dp数组,先物品,后背包,背包倒序遍历
⑤推导dp数组
代码
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {if (stones.size() == 1)return stones[0];int sum = 0;// 计算总重量for (int a : stones)sum += a;int target = sum / 2;vector<int> dp(target + 1, 0);// 先物品for (int i = 0; i < stones.size(); i++) {// 后背包for (int j = target; j >= stones[i]; j--) {// 01背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}// 分成两堆,一堆dp[target],另一堆sum-dp[target]return sum - dp[target] - dp[target];}
};
题目链接:494. 目标和
思路
数组中有若干数字,在每个数字前面放加号或者减号使得最后的结果为target,可以理解为组合问题,使用回溯算法。每次遇到数字都是两种选择,如果最后等于目标,方法种类做累加操作。这种方法的问题在于时间复杂度,每次都是两种选择,并且数组中有若干数字,时间复杂度呈指数增长。
既然有加减两种运算符,那就将数组分为两个子集,加法子集left,减法子集right,数组所有数字之和为sum,则sum = left + right,target = left - right,联立两式可得left = (sum+target)/2,如此只需要在数组中寻找若干数字,使其和等于left即可,剩下的就是减法子集。将问题转化成了01背包问题。
①dp数组,dp[j]表示装满容量为j的背包有dp[j]种方法
②递推公式,dp[j] += dp[j-nums[i]],举例,left=5时,装满需要dp[5],而dp[5]可以由dp[4]+dp[1]得到,以此类推
③dp数组初始化,dp[0] = 1,因为要进行累加操作,所以dp[0]取1
④遍历顺序,先物品,后背包,背包倒序遍历
⑤推导dp数组
代码
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 (abs(target) > sum)return 0;// 不能整除,说明如何构造都满足不了题目要求if ((sum + target) % 2 == 1)return 0;int left = (sum + target) / 2; // 背包容量vector<int> dp(left + 1, 0);dp[0] = 1; // dp数组初始化// 先物品for (int i = 0; i < nums.size(); i++) {// 后背包,倒序遍历for (int j = left; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[left];}
};
题目链接:474.一和零
思路
01背包的思路,数组中由若干物品,重量有两个维度,0的个数,1的个数;背包的容量也有两个维度,0和1的容量,m和n,最后求的是背包最多可以装多少件物品。
重量及容量涉及两个维度,加上所求的物品数量,总共三个变量,所以使用二维dp数组。
①dp数组,dp[i][j]表示容量为i个0和j个0的背包最多可以装dp[i][j]件物品
②递推公式,dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1),x表示当前物品0的个数,y表示当前物品1的个数
③dp数组初始化,dp[0][0]=0,容量都为0,装不了物品;dp数组中非0容量也初始化为0,这是因为在递推公式中涉及到max取最大值
④遍历顺序,先物品,后背包,背包倒序遍历
⑤推导dp数组
代码
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // dp数组及初始化// 01背包// 先物品for (string str : strs) {int x = 0; // 记录当前物品0的数量int y = 0; // 记录当前物品1的数量for (char a : str) {if (a == '0')x++;elsey++;}// 后背包,这里有两个维度0和1,倒序遍历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];}
};
总结
①01背包的基础知识已经理解了,但是如何将题目转换为01背包问题还需要熟练
②目前来说,将题目转换为01背包问题,主要是要找到背包与物品,然后确定每种物品只有一件
③01背包问题:装满背包的组合有多少种,最多能装多少件物品等
④dp数组含义以及递推公式的细节处理