自学内容网 自学内容网
自学内容网 > 正文

DP(3) | 0-1背包 | Java | LeetCode 1049, 494, 474 做题总结（474未完）

🕗 发布于 2024-07-14 08:13 java  leetcode  

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

和 LC 416.分割等和子集 类似

  • 思路（我没有思路）：
    两块石头相撞，这里没有想到的一个点是，相撞的两个石头要几乎相似
    以示例1为例，stones = [2,7,4,1,8,1]，如果从左到右相撞，得到的不是最优结果
    最优结果是相撞后重量最小的

    stones = [2,7,4,1,8,1]，总和23，一半为11，把这组石头分为一组11 一组12，他们相撞就是1

    0-1背包，M个物品放入容量为N的背包中，物品价值value、重量weight

递归五步：

  1. 确定dp数组（dp table）以及下标的含义
    背包重量 j 最大价值 dp[j] 最大重量 dp[j]
  2. 确定递推公式
    价值： dp[j] = Math.max(dp[j], dp[j-weight[i]] +value[i])
    重量：dp[j] = Math.max(dp[j], dp[j-stones[i]] +stones[i])
  3. dp数组如何初始化
    ① dp[0] = 0，其余也都是0
    ② 由于题目定义 1 <= stones.length <= 30; 1 <= stones[i] <= 100 所以极端情况下每个元素都为100，共30个元素，sum = 3000 , half = 1500
    int[]dp = new int [1501]
  4. 确定遍历顺序
    for物品 { for背包 }
  5. 举例推导dp数组
    求得一组石头的重量是 a = dp[target] ，另一组为 b= sum-dp[target]
    这里 b-a一定大于零，因为sum/2是向下取整的
  • ac-二维数组版本
    写的时候出错：① 递推公式写错 ② 初始化行列不分 ③ 初始化的值应为固定的value[0]
    这道题目的二维数据版本空间内存消耗很多。
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i=0; i<stones.length; i++) {
            sum += stones[i];
        }
        int bagSize = sum/2; // N
        // M = stones.length
        int[][] dp = new int[stones.length][bagSize+1]; //二维数组空间多很多

        //初始化第0行，物品0从哪里开始放
        for(int i=stones[0]; i<bagSize+1; i++) { // weight[0]
            dp[0][i] = stones[0];//value[0]错了
        }

        for(int i=1; i<stones.length; i++) {
            for(int j=1; j<bagSize+1; j++) {
                if(j<stones[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i] );
                }
            }
        }
        return sum-2*dp[stones.length-1][bagSize];
    }
}

在这里插入图片描述

  • ac-滚动数组版本
    写的过程中：递推公式又错了。
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;

        for(int i=0; i<stones.length; i++) {
            sum += stones[i];
        }

        int bagSize = sum/2; // N
        int M = stones.length; // M
        
        int[] dp = new int[bagSize+1];
        for(int i=0; i<M; i++) {
            for(int j=bagSize; j>=stones[i]; j--) { // weight[i]
            //两种情况，要么放，要么不放
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]); // 1 weight 2 value
            }
        }

        return sum-2*dp[bagSize];
    }
}

494. 目标和

思路

准备两个背包，一个背包package_a存放标记为正的元素，另一个背包package_b存放标记为负的元素。package_a - package_b = target。

设nums的元素和为sum, 可以列出方程：

package_a - package_b = target;
package_a + package_b = sum;

所以 package_a = (target + sum)/2。 所以根据题意给的target和sum，我们可以求出package_a的值。

那这道题就可以转化为：给定一个大小为package_a的背包，有多少种组合方式能把背包装满？ 妥妥的0-1背包。

元素放或者不放

答案

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i=0; i<nums.length; i++) {
            sum += nums[i];
        }        

        if(sum < Math.abs(target)){
            return 0;
        }

        if((sum + target) % 2 != 0) {
            return 0;
        }


        int bagSize = (target+sum)/2;
        int M = nums.length;

        int[][]dp = new int[M][bagSize+1];
        //首行-初始化
        if(nums[0] <= bagSize) {
            dp[0][nums[0]] = 1;
        }

        //首列-初始化
        int zeroNum = 0;
        for(int i=0; i<M; i++) {
            if(nums[i] == 0) {
                zeroNum++;
            }
            dp[i][0] = (int) Math.pow(2,zeroNum);
            // 有0的话，选或不选 2的x次方
            // 没有0，首列全部设为1？？什么意思
        }

        for(int i=1; i<M; i++) {
            for(int j=1; j<bagSize+1; j++) {
                if(nums[i]>j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
                }
            }
        }

        return dp[M-1][bagSize];
    }
}

难点

（1）错误状况 return 0的情况

  //如果target的绝对值大于sum，那么是没有方案的
  if (Math.abs(target) > sum) return 0;
  //如果(target+sum)除以2的余数不为0，也是没有方案的
  if ((target + sum) % 2 == 1) return 0;

（2）递推公式 dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]的由来

在这里插入图片描述
（3）数组的初始化

  • 首行初始化：只初始化二维数组M*N里的一个格子，就是 j=nums[0] 时，也就是 只选 物品0，其余都不选，此时情况赋为1。
  if(nums[0] <= bagSize) {
     dp[0][nums[0]] = 1;
  }
  • 首列初始化：
    （1）数组元素有0的话，选或不选 2的x次方
    （2）数组元素没有0，首列全部设为1？？什么意思
    dp[i][0] = 1，背包容量为0的时候，情况为1，或许可以理解为 这题本来就不是放背包，是求和？？
    看到别人的解释：任何一个物品，只要选择不取的方案，就能凑成0容量的背包
int zeroNum = 0;
for(int i=0; i<M; i++) {
    if(nums[i] == 0) {
        zeroNum++;
    }
    dp[i][0] = (int) Math.pow(2,zeroNum);
    // （1）数组元素有0的话，选或不选 2的x次方
    // （2）数组元素没有0，首列全部设为1？？什么意思
    // dp[i][0] = 1，背包容量为
}

出错点

① Math.pow(); 之前要写 (int) 强制类型转换

Line 32: error: incompatible types: possible lossy conversion from double to int
 dp[i][0] = Math.pow(2,zeroNum);

打印dp（为了方便理解）

（1）

  int[]nums = {1,1,1,1,1};
  int target = 3;
  • 初始化

在这里插入图片描述

  • 最终dp

在这里插入图片描述

（2）打印

  int[]nums = {0,1,0,1,1};
  int target = 1;
  • 初始化

在这里插入图片描述

  • 最终dp

在这里插入图片描述

474.一和零

java

  • 除以 2 ：int target = sum >> 1;

  • 强制类型转换：int x = (int)Math.pow(a, b); 意思是 a的b次方
    public static double pow(double 基数，double 幂次)


原文地址：https://blog.csdn.net/yavlgloss/article/details/140396295

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024