当前位置: 首页 > article >正文

代码随想录算法训练营第四十二天 _ 动态规划_01背包问题、416.分割等和子集。

学习目标:

动态规划五部曲:
① 确定dp[i]的含义
② 求递推公式
③ dp数组如何初始化
④ 确定遍历顺序
⑤ 打印递归数组 ---- 调试
引用自代码随想录!

60天训练营打卡计划!

学习内容:

二维数组处理01背包问题

  • 听起来思路很简单,但其实一点也不好实现。
  • 动态规划五步曲:
    ① 确定dp[i][j]的含义 : 任取[0, i]的物品后放进容量为j的背包 所能放的 最大价值
    ② 求递推公式 : dp[i][j] = max(dp[i-1][j] , dp[i-1][ j - weight[i] ] + value[i])
    Ⅰ 不放物品 i : dp[i-1][j]
    Ⅱ 放物品 i : dp[i-1][j - weight[i]] + value[i]
    ③ dp数组如何初始化 : 按下表的第一行和第一列赋值,其中箭头都是继承来的值,画圈的表示自己取得了最大值。请添加图片描述
    ④ 确定遍历顺序 : 先物品后背包(行) / 先背包后物品(列)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //m,n分别代表物品种类和背包容量
        int itemSize = 0,bagSize = 0;
        Scanner sc = new Scanner(System.in);
        //获取itemSize和bagSize的值
        itemSize = sc.nextInt();
        bagSize = sc.nextInt();
        //初始化对应的重量数组和价值数组
        int[] weight = new int[itemSize];
        int[] value = new int[itemSize];
        //这两个都是物品的属性,大小只和物品数量有关
        for(int i = 0;i < itemSize;i++){
            weight[i] = sc.nextInt();
        }
        for (int i = 0;i < itemSize;i++){
            value[i] = sc.nextInt();
        }
        
        // int[] weight = {1,3,4};
        // int[] value = {15,20,30};
        // int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        int itemSize = weight.length;
        // dp数组的含义是:在[0,i]件物品中选择是否放入背包 的 最大价值
        int[][] dp = new int[itemSize][bagSize+1];
        
        // 初始化dp数组,默认都为0.
        // 只放一件物品时的初始化
        for(int j = weight[0]; j < bagSize+1; j++){
            dp[0][j] = value[0];
        }
        
        // 正常的为dp数组赋值,依赖左上位置的其他的dp值
        for(int i = 1; i < itemSize; i++){
            // j是背包容量
            for(int j = 1; j < bagSize+1; j++){
                // 如果容量不够放入新的物品,则从上一行继承
                if(j < weight[i])   dp[i][j] = dp[i-1][j];
                // 如果容量可以放入新的物品,则从上一行的左侧继承
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
            }
        }
        System.out.println(dp[itemSize-1][bagSize]);
        
        // 打印dp数组
        // for (int i = 0; i < goods; i++) {
        //     for (int j = 0; j <= bagSize; j++) {
        //         System.out.print(dp[i][j] + "\t");
        //     }
        //     System.out.println("\n");
        // }
    }
}

一维数组处理01背包问题

  • 动态规划五步曲:
    ① 确定dp[j]的含义 : 任取物品放进容量为j的背包 所能放的 最大价值
    ② 求递推公式 : dp[j] = max(dp[j] , dp[j - weight[i]] + value[i])
    Ⅰ 不放物品 i : dp[j]
    Ⅱ 放物品 i : dp[j - weight[i]] + value[i]
    ③ dp数组如何初始化 : 初始值全部附0,长度为容量的长度加1(j+1)
    ④ 确定遍历顺序 : 必须先物品后背包(行),且便利背包大小时,必须使用倒序的顺序遍历。(为了防止一个物品被使用多次,倒叙遍历时相同的物品仅能被取用一次)

请添加图片描述

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //m,n分别代表物品种类和背包容量
        int itemSize = 0,bagSize = 0;
        Scanner sc = new Scanner(System.in);
        //获取itemSize和bagSize的值
        itemSize = sc.nextInt();
        bagSize = sc.nextInt();
        //初始化对应的重量数组和价值数组
        int[] weight = new int[itemSize];
        int[] value = new int[itemSize];
        //这两个都是物品的属性,大小只和物品数量有关
        for(int i = 0;i < itemSize;i++){
            weight[i] = sc.nextInt();
        }
        for (int i = 0;i < itemSize;i++){
            value[i] = sc.nextInt();
        }
        
        // int[] weight = {1,3,4};
        // int[] value = {15,20,30};
        // int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp一维数组
        int goods = weight.length;  // 获取物品的数量
        int[] dp = new int[bagSize + 1];

        // 初始化dp数组
        // 创建数组后,其中默认的值就是0
        
        // 填充dp数组
        for (int i = 0; i < goods; i++) {
            // 必须使用倒叙遍历背包大小
            for (int j = bagSize; j > 0; j--) {
                // 防止越界错误
                if (j < weight[i]) {
                    dp[j] = dp[j];
                } else {
                    dp[j] = Math.max(dp[j] , dp[j-weight[i]] + value[i]);
                }
            }
        }
        
        System.out.print(dp[bagSize]);

        // 打印dp数组
        // System.out.print(dp[goods-1][bagSize] + "\n");
        // for (int i = 0; i < goods; i++) {
        //     for (int j = 0; j <= bagSize; j++) {
        //         System.out.print(dp[i][j] + "\t");
        //     }
        //     System.out.println("\n");
        // }
    }
}

在这里插入图片描述

416.分割等和子集

该题目可以等效为一个重量和价值相等的01背包问题,所以使用一维的数组就可。

  • 因为题目问的是可不可以分为两个等和子集,没有问具体应该怎么分。
  • 动态规划五步曲:
    ① 确定dp[j]的含义 : 容量为j的背包的最大价值
    ② 求递推公式 : dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
    ③ dp数组如何初始化 : 全部为零
    ④ 确定遍历顺序 : 先遍历物品,再倒叙遍历背包。
  • 实现的特别巧妙,将该问题视为一个重量和价值相等的01背包问题,将目标和作为背包的重量,只要背包重量最大时能达到目标和的价值,即找到了一组数满足目标,那么此时该数组就可以分为等和的子集。
class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for(int num :nums){
            total += num;
        }
        if(total % 2 == 1)   return false;
        // target就是背包的最大重量
        int target = total / 2;

        int[] dp = new int[target+1];

        // 初始化:数组定义的时候已经被全部赋值0

        // 递推函数
        for(int i = 0; i < nums.length; i++){
            for(int j = target; j >= 0; j--){
                if(j < nums[i])   dp[j] = dp[j];
                else{
                    dp[j] = Math.max(dp[j], dp[j - nums[i]]+nums[i]);
                }
            }
        }

        // 因为target是整除2得到的,所以只要能找到一组数使其和为target
        // 剩下的数的和也是target
        if(dp[target] == target)   return true;
        else    return false;

    }
}

学习时间:

  • 上午两个半小时,整理文档半小时。

http://www.kler.cn/news/161053.html

相关文章:

  • 医院有HIS系统,为什么还要开发预约挂号小程序?数据如何互通?
  • 前端笔记(三)CSS 盒子模型
  • ★538. 把二叉搜索树转换为累加树
  • PHP使用HTTP代码示例模板
  • gpt3、gpt2与gpt1区别
  • 深入理解 Java 虚拟机(JVM)从入门到精通
  • 使用GPT-4V解决Pycharm设置问题
  • 西工大计算机学院计算机系统基础实验一(函数编写11~14)
  • Java程序员,你掌握了多线程吗?
  • 【运维面试100问】(七)ceph基础题面试
  • 「神印王座」萝莉女神小六打劫,白送10万功勋点,王原原恋人登场
  • 掌汇云 | 全场景数据追踪,多维了解用户偏好,提高运营效率
  • python入门级简易教程
  • C语言二叉树的基本概念(一)
  • 猫头虎分享ubuntu20.04下VSCode无法输入中文解决方法
  • ProEasy机器人案例:电池边包胶
  • IoT DC3 是一个基于 Spring Cloud 全开源物联网平台 linux docker部署傻瓜化步骤
  • 图解系列--HTTPS,认证
  • Linux AMH服务器管理面板本地安装与远程访问
  • C++ Primer Plus第十五章笔记
  • 第4节:Vue3 布尔属性
  • H5: 按钮的点击热区
  • 解析操作系统是如何启动起来的?
  • Django 模板引擎 (四)
  • 分享5款在各自领域遥遥领先的软件
  • 【IEEE独立出版】2024第四届神经网络、信息与通信工程国际学术会议(NNICE 2024)
  • 从cot到agent的survey视频笔记
  • 2023.12.4 GIT的概念和组成
  • 几分钟在Ubuntu搭建本地Emlog博客网站并发布至公网无需购买域名服务器
  • 计网Lesson5 - MAC 地址与 ARP