代码随想录算法训练营第四十二天 _ 动态规划_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…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

归并排序:分治思想的高效排序
目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法,由约翰冯诺伊曼在1945年提出。其核心思想包括: 分割(Divide):将待排序数组递归地分成两个子…...

Canal环境搭建并实现和ES数据同步
作者:田超凡 日期:2025年6月7日 Canal安装,启动端口11111、8082: 安装canal-deployer服务端: https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...