JLUVicent

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

 
  • 2023年 03月29日
  • 0 阅读

day43

1049.最后一块石头的重量II

题目链接：1049. 最后一块石头的重量 II

解题思路：参考 视频

尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了

动态规划五部曲：

1.确定dp[j]的含义及下标：dp[j]表示容量为j的背包所能背的最大价值

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

3.初始化：将dp数组都初始化为0

4.确定遍历顺序：先遍历物品再遍历背包

for (int i = 0; i < stones.size(); i++) { // 遍历物品
    for (int j = target; j >= stones[i]; j--) { // 遍历背包
        dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}

5.举例推导打印dp数组

1049.最后一块石头的重量II

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        vector<int> dp(1501,0);
        for( int i = 0; i < stones.size(); i++){
            sum += stones[i];
        }
        int target = sum / 2;
        for( int i = 0; i < stones.size(); i++){
            for( int j = target; j >= stones[i]; j--){
                dp[j] = max( dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum-2*dp[target];

    }
};

494.目标和

题目链接：494. 目标和

解题思路：参考 视频

首先使表达式结果为target，正数用left，负数用right $$ left + right = sum \newline

left - right = taget\newline left = (target + sum)/2 $$

加法总和为x,减法总和就是sum - x,问题转化为装满容量为x的背包，有几种方法

x就是背包容量。

首先应该判断，如果(sum + target) % 2 != 0 ,直接返回0，此时不可能满足条件

if( abs(target) > sum)也是直接返回0

每个物品只取一次，因此为01背包问题。

1.确定dp[j]及下标的含义：填满容量为j的背包有dp[j]种方法

2.确定递推公式：dp[j] += dp[j - nums[i]];

3.dp数组初始化：dp[0] = 1; 如果初始化为0则递推结果都是0，不用硬解释其本身的意义。

4.确定遍历顺序：物品在外，背包在内

5.举例推导dp数组

img

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 时间：O(n*m)
        // 空间：O(m)
        int sum = 0; 
        for( int i = 0; i < nums.size(); i++){
            sum += nums[i];
        }
        if( (sum + target) % 2 == 1) return 0;
        if( abs(target) > sum ) return 0;
        int left = (sum + target) / 2;	// left表示正数和
        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.一和零

题目链接：474. 一和零

解题思路：参考 视频

strs数组中的元素就是物品，每个物品都是一个

m和n相当于背包，两个维度的背包

动态规划五部曲：

1.确定dp数组及下标的含义：$dp[i][j]$:最多有i个0和j个1的strs的最大子集大小为$dp[i][j]$

2.确定递推公式：$dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)$,这块相当于把纯01背包里面的weight变为zeroNum和oneNum了，value就是1.

3.dp数组初始化：$dp[0][0] = 0$全为0即可，之后max()推导时候会覆盖掉

4.确定遍历顺序：外层for遍历物品，内层for遍历背包

for (string str : strs) { // 遍历物品
    int oneNum = 0, zeroNum = 0;
    for (char c : str) {
        if (c == '0') zeroNum++;
        else oneNum++;
    }
    for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！这块没有区别
        for (int j = n; j >= oneNum; j--) {
            dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
    }
}

5.打印dp数组

474.一和零

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));//初始化dp数组
        for( string str:strs){
            int oneNum = 0,zeroNum = 0;
            for( char c:str){
                if( c == '0') zeroNum++;
                else oneNum++;
            }        
            for( int i = m; i >= zeroNum; i--){//倒序遍历背包
                for( int j = n; j >= oneNum; j--){  //倒序遍历背包
                dp[i][j] = max( dp[i][j],dp[i-zeroNum][j-oneNum]+1);    //这里加一表示容量加1
                }
            }
        }
        return dp[m][n];
    }
};

01背包总结

纯0-1背包

给定背包容量，装满背包的最大价值是多少？

416.分割等和子集

给定背包容量，能不能装满这个背包？

1049.最后一块石头的重量II

给定背包容量，尽可能装，最多能装多少？

494.目标和

给定背包容量，装满背包有多少种方法？

474.一和零

给定背包容量，装满背包最多有多少种物品

搜索