代码随想录算法训练营第四十二天 _ 动态规划_01背包问题。
学习目标:
动态规划五部曲:
① 确定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];// 如果容量可以放入新的物品,则从上一行的左侧继承elsedp[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");// }}
}
学习时间:
- 上午两个半小时,整理文档半小时。
相关文章:

代码随想录算法训练营第四十二天 _ 动态规划_01背包问题。
学习目标: 动态规划五部曲: ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录! 60天训练营打卡计划! 学习内容: 二维数组处理01背包问题 听起来…...

会话 cookie 及隐私的那些事
什么是会话 Cookie? 会话 Cookie 的概念非常简单。 会话 Cookie,也称为临时 Cookie 或内存 Cookie,是网站在浏览会话期间存储在用户计算机或设备上的小数据片段。 它是由网站生成并由您的浏览器存储和使用的多种 Cookie 之一。 常规 Cookie 或“持久”Cookie 是通常在您的…...
前端知识笔记(二十九)———MySQL通配符和正则表达式
一、通配符 1.% 匹配0,1,多个字符,但不匹配NULL 2._ 匹配单个字符 3.[charlist] 匹配字符列中的任何单一字符 4.[^charlist] 或 [!charlist] 匹配不在字符列中的任何单一字符 二、正则表达式 通配符的LIKE替换为REGEXP LIKE 匹配整个列&…...
C#网络编程(System.Net.Sockets命名空间)
目录 一、Socket类 1.示例源码 2.生成效果 二、TcpClient类和TcpListener类 1.示例源码 2.生成效果 三、UdpClient类 1.示例源码 2.生成效果 System.Net.Sockets命名空间主要提供制作Sockets网络应用程序的相关类,其中Socket类、TcpClient类、TcpListener类…...
linux 系统重装 ssh 连接失败
一.错误描述 WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED 二.解决方案 输入以下指令: ssh-keygen -R XXX(ip地址) 按照我的例子(ip:10.165.7.136),会返回以下信息: 重新尝试连…...
stream流操作List对象,指定属性,取差集、交集
差集 // 差集 (list1 - list2 list1 中不同数据)List<Person> reduce1 list1.stream().filter(a -> !list2.stream().map(b -> b.getAge() "&" b.getName()).collect(Collectors.toList()).contains(a.getAge() "&" a.getName()…...
计算机相关行业在大数据库时代下的潮流和趁势
还记得当初自己为什么选择计算机? 随着数据的爆炸性增长,数据科学和数据分析成为了热门的领域。这些专业涉及处理和分析大规模数据集的技术和方法,以从中提取有价值的信息和洞察。数据科学家和数据分析师在各个行业中的需求不断增加…...

Mac苹果视频剪辑:Final Cut Pro Mac
Final Cut Pro是一款由Apple公司开发的专业视频非线性编辑软件,是业界著名的视频剪辑软件之一。它最初发布于1999年,是Mac电脑上的一款独占软件。Final Cut Pro具有先进的剪辑工具、丰富的特效和颜色分级、音频处理等功能,使得用户可以轻松地…...
高德Map
使用 官网:JS API 结合Vue使用 npm i amap/amap-jsapi-loader --saveimport AMapLoader from amap/amap-jsapi-loader;marker的属性、事件、方法 https://lbs.amap.com/api/javascript-api-v2/documentation#marker 自定义marker 为创建的 Marker 指定自定义图…...

SSM新闻发布管理系统
SSM毕设分享 序号1:SSM新闻发布管理系统 1 项目简介 Hi,各位同学好,这里是郑师兄! 今天向大家分享一个毕业设计项目作品【SSM新闻发布管理系统】 师兄根据实现的难度和等级对项目进行评分(最低0分,满分5分) 难度系数…...

客户销售目标拆解:数据驱动的方法和策略
写在开头 在当今竞争激烈的商业环境中,企业需要更加精准地制定销售目标以实现业务增长。数据驱动的方法在这一过程中扮演着关键的角色,帮助企业深入了解客户特征、行为和需求。本篇博客将深入探讨销售目标拆解在企业管理中的重要性,并介绍如何利用数据驱动的方法和策略来制…...

“丝路电商”与泛欧在线公共采购平台Peppol
近期上海商务委员会公布《关于在上海市创建“丝路电商”合作先行区的方案》(以下简称方案),方案中提出:“全面贯彻落实党的二十大精神,立足新发展阶段,完整、准确、全面贯彻新发展理念,加快构建…...

今日思考 -- 创新领导力(CIO)读后感
收获3个观点: 1 ,IT DT 商业,才是未来IT人的出路之一 ! 2 ,在CXO中,CIO像CEO一样,具备了整个企业的业务全视角 ,同时也更具解决 ‘’系统性‘’问题的能力 ! 3 &…...
Python实现Excel自动化
个人网站 文章首发于公众号:小肖学数据分析 Excel是办公自动化的关键工具之一,用于数据存储、处理和分析。 Python通过 openpyxl 库,提供了强大的Excel操作能力,让我们可以读取、写入、修改和创建复杂的Excel文件。 安装 open…...
WT2605-24SS高品质录音语音芯片:实现五种变音效果,为音频应用增添无限创意
在音频技术的世界里,录音芯片作为声音处理和传输的核心部件,一直以来都承载着人们对高品质音频的追求。而唯创知音推出的WT2605-24SS高品质录音语音芯片则在此基础上更进一步,带来了五种独特的变音效果,为音频应用注入了无限的创意…...

最美早安心语问候朋友们,祝你心情美好,万事如意
1、真诚的友谊,不会忘记,永远的朋友,每天想起。生活就是大海,朋友就是浪花,大海因有了浪花而美丽,生活有了朋友而甜蜜;祝福依旧,问候依然,祝朋友们开心快乐每一天……大家…...
2312skia,16画布
创建SkCanvas 首先,阅读SkCanvasAPI概述. Skia有多个接收SkCanvas绘图命令的后端.每个后端都有创建SkCanvas的独特方式.本页给出了每个示例: 光栅化 光栅化后端将绘画到可由Skia或客户管理的内存块. 推荐用管理画布命令要绘画内存对象的SkSurface为Raster和Ganesh后端创建画…...

mysql文本类型的最大长度限制
mysql支持很多类型,不同的文本有不同的长度限制。可以根据实际需要进行选择。 TINYBLOB, TINYTEXT L 1 bytes, where L < 2^8 (255 Bytes) BLOB, TEXT L 2 bytes, where L < 2^16 (64 Kilobytes) MEDIUMBLOB, MEDIUMTEXT L 3 b…...

ASP.NET《数据库原理及应用技术》课程指导平台的开发
1.1 系统设计目标 研制《数据库原理及应用技术》课程指导平台在功能上可以满足网络课堂教学活动的需要,在Internet上实现教学活动的各个环节。系统的基本设计原则有:先进性与方便性原则、功能实用性原则、开放性与可扩展性原则等。系统设计时采用较好的…...

OSHI-操作系统和硬件信息库
文章目录 引言一、快速入门1.1 OSHI的简介1.2 引入依赖1.3 涉及的包(package)1.4 涉及的核心类 二、操作系统信息:OperatingSystem2.1 总揽2.2 文件系统信息:FileSystem2.3 网络参数信息:NetworkParams2.4 进程信息&am…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...

Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...

算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...

高分辨率图像合成归一化流扩展
大家读完觉得有帮助记得关注和点赞!!! 1 摘要 我们提出了STARFlow,一种基于归一化流的可扩展生成模型,它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流(TARFlow&am…...

GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...