day42 动态规划part4

news/2024/5/26 20:46:55/文章来源:https://blog.csdn.net/weixin_43889767/article/details/136636705

先遍历物品还是先遍历背包二刷再考虑吧。累了,不想停留太久。

在这里插入图片描述

背包问题 二维 (卡码网题目)

在这里插入图片描述

各种解释:

要理解的是这个表格每一个格子都是当前所处情况的最大价值,我们用已经推导出的最大价值来推导当前情况的最大价值。
在这里插入图片描述
在这里插入图片描述

package DP;// i-1是指能选择的物品有i-1个而不一定真的放了i-1个物品
// dp【i】【j】 表示背包容量为 j 时,从 0..i 类物品种选取,可以获得的最大价值
// 如果有的朋友不理解对放物品i时为什么要是 j - weight【i】,这里可以理解为背包需要留出这个物品i的容量才可以放物品i
public class BagProblem {public static void main(String[] args) {int[] weight = {4,3,1};int[] value = {30,20,15};int bagSize = 4;testWeightBagProblem(weight,value,bagSize);}public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){int[][] dp = new int [weight.length][bagSize + 1];// 初始化dp数组/*** 初始化 dp 数组做了简化(给物品增加冗余维)。这样初始化dp数组,默认全为0即可。* dp[i][j] 表示从下标为[0 - i-1]的物品里任意取,放进容量为j的背包,价值总和最大是多少。* 其实是模仿背包重量从 0 开始,背包容量 j 为 0 的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为 0。* 可选物品也可以从无开始,也就是没有物品可选,即dp[0][j],这样无论背包容量为多少,背包价值总和一定为 0。* @param weight  物品的重量* @param value   物品的价值* @param bagSize 背包的容量*/// 创建数组后,其中默认的值就是0for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = value[0];}// 填充 dp 数组for (int i = 1; i < weight.length; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]) { // 容量不够,放不进去dp[i][j] = dp[i - 1][j];} else { // 能放进去/*** 当前背包的容量可以放下物品i* 那么此时分两种情况:*    1、不放物品i*    2、放物品i* 比较这两种情况下,哪种背包中物品的最大价值最大*/dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);}// 打印dp数组(自己整个数组试试就知道了)System.out.println("i = " + i + "\t" + "j = " + j);for (int k = 0; k < weight.length; k++) {for (int z = 0; z <= bagSize; z++) {System.out.print(dp[k][z] + "\t");}System.out.println("\n");}}}}}

背包问题 一维(滚动数组) (卡码网题目,和上面那个题目是一样的)

难点在于,把二维数组变成了一维,相当于把上一行的数据复制到了下一行,不断滚动。最大的差异在于,遍历的顺序变成了从后往前,其实是没问题的,因为算本行数据只需要用到上一行的数据,本行前面的数据用不上,所以可以从后往前。倒序的时候左边元素再刷新前都是上一层的数据,但正序就不一样了,正序的时候,左边的元素刚刚刷新过,也就是左边的元素已经是本层的了,意味着什么 这样会导致一个物品反复加好几次。具体解释见下面截图:

在这里插入图片描述

难点:初始化也变了,因为从后往前遍历,所以可以内化到for循环里去。一维和二维的初始化其实是一个道理。你可以理解成二维数组初始化的时候,在物品0上面还有一个物品-1代表一个重量和价值都等于0的物体。 dp[j - weight[i]] 为什么不会越界?因为for循环里写了j > = weight[i] !!!

在这里插入图片描述

for循环中途有一个条件不满足会直接退出,如下演示:

在这里插入图片描述

 public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWight = 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen = weight.length;//定义dp数组:dp[j]表示背包容量为j时,能获得的最大价值int[] dp = new int[bagWeight + 1];//遍历顺序:先遍历物品,再遍历背包容量for (int i = 0; i < wLen; i++){for (int j = bagWeight; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}//打印dp数组for (int j = 0; j <= bagWeight; j++){System.out.print(dp[j] + " ");}}

416. 分割等和子集

中等
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

难点:这道题目就是一道01背包应用类的题目,需要我们拆解题目,然后套入01背包的场景。01背包相对于本题,主要要理解,题目中物品是nums[i],重量是nums[i],价值也是nums[i],背包体积是sum/2。就相当于,给你一个体积为sum/2的背包,让你挑选一种放东西的方法,使得放的东西最多,最多是多少,当然是放满,也就是sum/2,如果没放这么多,说明就是放不满,返回false。

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) sum += num;if (sum % 2 == 1) return false; // 和为奇数,不可等分int dp[] = new int [sum / 2 + 1];for (int i = 0; i < nums.length; i++) {for (int j = dp.length - 1; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[dp.length - 1] == sum / 2;}
}
public class Solution {public static void main(String[] args) {int num[] = {1,5,11,5};canPartition(num);}public static boolean canPartition(int[] nums) {int len = nums.length;// 题目已经说非空数组,可以不做非空判断int sum = 0;for (int num : nums) {sum += num;}// 特判:如果是奇数,就不符合要求if ((sum %2 ) != 0) {return false;}int target = sum / 2; //目标背包容量// 创建二维状态数组,行:物品索引,列:容量(包括 0)/*dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数每个数只能用一次,使得这些数的和恰好等于 j。*/boolean[][] dp = new boolean[len][target + 1];// 先填表格第 0 行,第 1 个数只能让容积为它自己的背包恰好装满  (这里的dp[][]数组的含义就是“恰好”,所以就算容积比它大的也不要)if (nums[0] <= target) {dp[0][nums[0]] = true;}// 再填表格后面几行//外层遍历物品for (int i = 1; i < len; i++) {//内层遍历背包for (int j = 0; j <= target; j++) {// 直接从上一行先把结果抄下来,然后再修正dp[i][j] = dp[i - 1][j];//如果某个物品单独的重量恰好就等于背包的重量,那么也是满足dp数组的定义的if (nums[i] == j) {dp[i][j] = true;continue;}//如果某个物品的重量小于j,那就可以看该物品是否放入背包//dp[i - 1][j]表示该物品不放入背包,如果在 [0, i - 1] 这个子区间内已经有一部分元素,使得它们的和为 j ,那么 dp[i][j] = true;//dp[i - 1][j - nums[i]]表示该物品放入背包。如果在 [0, i - 1] 这个子区间内就得找到一部分元素,使得它们的和为 j - nums[i]。if (nums[i] < j) {dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];}}}for (int i = 0; i < len; i++) {for (int j = 0; j <= target; j++) {System.out.print(dp[i][j]+" ");}System.out.println();}return dp[len - 1][target];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1005875.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

用chatgpt写论文重复率高吗?如何降低重复率?

ChatGPT写的论文重复率很低 ChatGPT写作是基于已有的语料库和文献进行训练的&#xff0c;因此在写作过程中会不可避免地引用或借鉴已有的研究成果和观点。同时&#xff0c;由于ChatGPT的表述方式和写作风格与人类存在一定的差异&#xff0c;也可能会导致论文与其他文章相似度高…

LiveGBS流媒体服务器中海康摄像头GB28181公网语音对讲、语音喊话的配置

LiveGBS海康摄像头国标语音对讲大华摄像头国标语音对讲GB28181语音对讲需要的设备及服务准备 1、背景2、准备2.1、服务端必备条件&#xff08;注意&#xff09;2.2、准备语音对讲设备2.2.1、不支持跨网对讲示例2.2.2、 支持跨网对讲示例 3、开启音频开始对讲4、搭建GB28181视频…

Linux学习笔记(一)Linux基本指令

文章目录 前言目录常见命令1. pwd 打印当前所在路径2. cd 改变路径、切换路径3. 家目录 回到顶级目录4. 当前路径和上一路径5. 上一次路径6. 绝对路径和相对路径7. ls 列出目录内容8. mkdir 创建目录9. rmdir 删除目录10. touch 创建文件11. mv 修改文件目录、移动路径12. cp 复…

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:RemoteWindow)

远程控制窗口组件&#xff0c;可以通过此组件控制应用窗口&#xff0c;提供启动退出过程中控件动画和应用窗口联动动画的能力。 说明&#xff1a; 该组件从API Version 9开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 该组件为系统接口。…

【Axure高保真原型】下拉列表切换图表

今天和大家分享通过下拉列表动态切换统计图表的原型模板&#xff0c;我们可以通过下拉列表选择要显示的图表&#xff0c;包括柱状图、条形图、饼图、环形图、折线图、曲线图、面积图、阶梯图、雷达图&#xff1b;而且图表数据可以在左侧表格中动态维护&#xff0c;包括增加修改…

基于php的用户登录实现(v2版)(持续迭代)

目录 版本说明 数据库连接 登录页面&#xff1a;login.html 登录处理实现&#xff1a;login.php 用户欢迎页面&#xff1a;welcome.php 密码修改页面&#xff1a;change_password.html 修改执行&#xff1a;change_password.php 用户注册页面&#xff1a;register.html …

lvs+keepalive

虚拟路由冗余协议(Virtual Router Redundancy Protocol&#xff0c;简称VRRP) VRRP能够在不改变组网的情况下&#xff0c;将多台路由器虚拟成一个虚拟路由器&#xff0c;通过配置虚拟路由器的IP地址为默认网关&#xff0c;实现网关的备份。 协议版本: VRRPv2&#xff08;常用&…

网络通信另个角度的认识(进程间通信),端口号(为什么要有,和pid的关系,分类,如何封装,和进程的定位原理+对应关系),客户端如何拿到服务端的port

目录 另一个角度认识网络通信 端口号 引入 -- 为什么要有端口号 问题 解决 端口号和pid 举例 介绍 分类 知名端口 注册端口 动态端口 客户端如何知道服务端的端口号 封装端口号 定位原理 进程和端口号的对应关系 数据如何被上层进程读到 另一个角度认识网络…

深入理解Vue3中利用mitt:实现轻量级事件监听与触发

在 Vue3 中&#xff0c;父组件和子组件之间可以通过一些方式进行通信。其中&#xff0c;父组件向子组件通信主要有两种方式&#xff1a;传值和调用子组件的方法。 一、父组件向子组件传值 当父组件需要向子组件传递数据时&#xff0c;可以通过属性绑定的方式来实现。父组件可…

【Redis】redis持久化

redis 持久化 Redis是内存数据库&#xff0c;数据都是存储在内存中&#xff0c;为了避免进程退出导致数据的永久丢失&#xff0c;需要定期将Redis中的数据以某种形式(数据或命令)从内存保存到硬盘&#xff1b;当下次Redis重启时&#xff0c;利用持久化文件实现数据恢复。除此之…

leetcode 热题 100_删除链表的倒数第 N 个结点

题解一&#xff1a; 递归&#xff1a;利用递归栈逆向遍历链表&#xff0c;并用全局变量记录当前遍历的是倒数第几位节点&#xff0c;当遍历到待删节点的上一位节点时&#xff0c;node.nextnode.next.next删除待删节点。需要注意当删除的是头节点时&#xff0c;直接return head.…

Codeforces Round 933 (Div. 3) A~D

比赛链接 : codeforces.com/contest/1941 A . Rudolf and the Ticket 直接暴力即可 ; #include<bits/stdc.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl \n #define lowbit(x) (x&(-x)) #define sz(a) (int)a.size() #define p…

Docker进阶:深入了解容器数据卷

Docker进阶&#xff1a;深入了解容器数据卷 一、前言二、容器数据卷的作用三、容器数据卷的使用方法四、实战--使用docker部署前端项目&#xff08;数据卷挂载&#xff09;4.1 重要&#xff1a;准备工作&#xff0c;先在本地创建挂载目录4.2 启动一个临时的nginx容器&#xff0…

“光谱视界革新:ChatGPT在成像光谱遥感中的智能革命“

遥感技术主要通过卫星和飞机从远处观察和测量我们的环境&#xff0c;是理解和监测地球物理、化学和生物系统的基石。ChatGPT是由OpenAI开发的最先进的语言模型&#xff0c;在理解和生成人类语言方面表现出了非凡的能力。本文重点介绍ChatGPT在遥感中的应用&#xff0c;人工智能…

前端去除网页水印

按F12&#xff0c;打开开发者工具面板&#xff0c;然后直接在样式搜索backgroud 然后直接取消backgroud 的复选框即可。

多数问题求解之蒙特卡洛与分治法

多数问题&#xff08;Majority Problem&#xff09;是一个有多种求解方法的经典问题&#xff0c;其问题定义如下&#xff1a; 给定一个大小为 n n n的数组&#xff0c;找出其中出现次数超过 n / 2 n/2 n/2的元素 例如&#xff1a;当输入数组为 [ 5 , 3 , 5 , 2 , 3 , 5 , 5 ] […

SkyEye:助力飞行器状态控制系统仿真

飞行器与常见的航天器一样&#xff0c;属于安全关键领域的大型复杂设备&#xff0c;对安全性、可靠性有着极高的要求。为保证稳定飞行&#xff0c;需要对目标对象进行实时跟踪&#xff0c;通过发出正确的修正偏差指令来操纵飞行器改变飞行姿态&#xff0c;因此对飞行器状态控制…

leetcode刷题(javaScript)——分治思想(二分查找、快速排序)相关场景题总结

分治思想是一种将问题分解成更小的子问题&#xff0c;然后解决子问题并将结果合并的算法设计策略。二分查找、快速排序和折半查找都属于分治思想的经典算法。在leetcode里&#xff0c;分治思想一般结合其他场景出现&#xff0c;构成复合型题目。但是在看题时一定要了解能否用分…

考研数学|武忠祥「高数」+李永乐「线代」刷题指南

如果你全程都决定跟着武忠祥老师和李永乐老师&#xff0c;一张表格教会你如何买资料&#xff0c;听课以及使用这些资料&#xff1a; 上面的方法很详细了&#xff0c;大家照着做就行了&#xff0c;关键是大家实际操作的过程中可能会遇到各种问题&#xff0c;这也是我在考研备考中…

隧道技术和代理技术(三)

隧道技术 知识点 -隧道技术&#xff1a;解决不出网协议上线的问题&#xff08;利用出网协议进行封装出网&#xff09; -代理技术&#xff1a;解决网络通讯不通的问题&#xff08;利用跳板机建立节点后续操作&#xff09; 内环境示意图&#xff0c;方便理解 思路&#xff1a;…