Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ
完全背包
题目
文章讲解
视频讲解
完全背包和0-1背包的区别在于:物品是否可以重复使用
思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次放入背包,从而求解完全背包问题。
对于完全背包问题,需要对内层循环进行调整,以确保每种物品可以被选择多次放入背包。
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); // 研究材料种类int V = sc.nextInt(); // 行李箱空间int[] values = new int[N]; // 物品价值int[] weight = new int[N]; // 物品重量// 依次输入每种物品的重量和价值for (int i = 0; i < N; i++) {weight[i] = sc.nextInt(); // 物品重量values[i] = sc.nextInt(); // 物品价值}int[] dp = new int[V + 1]; // 动态规划数组for (int i = 0; i < N; i++) {for (int j = weight[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); // 动态规划状态转移方程}}System.out.println(dp[V]); // 输出结果}
}
一维0-1背包求解法示例如下
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); // 研究材料种类int V = sc.nextInt(); // 行李箱空间int[] values = new int[N]; // 物品价值int[] weight = new int[N]; // 物品重量// 依次输入每种物品的重量和价值for (int i = 0; i < N; i++) {weight[i] = sc.nextInt(); // 物品重量values[i] = sc.nextInt(); // 物品价值}int[] dp = new int[V + 1]; // 动态规划数组for (int i = 0; i < N; i++) {for (int j = V; j >= weight[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); // 动态规划状态转移方程}}System.out.println(dp[V]); // 输出结果}
}
对比:
-
完全背包:
-
0-1背包:
518. 零钱兑换 II
题目
文章讲解
视频讲解
思路:
- dp[j]:凑成总金额j的货币组合数为dp[j]
- 递推公式:dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加
- 初始化需要注意 dp[0]=1;
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
}
377. 组合总和 Ⅳ
题目
文章讲解
视频讲解
思路:
如果求组合数就是外层for循环遍历物品,内层for遍历背包;
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.length; j++) {if (i >= nums[j])dp[i] += dp[i - nums[j]];}}return dp[target];}
}
相关文章:
Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ
完全背包 题目 文章讲解 视频讲解 完全背包和0-1背包的区别在于:物品是否可以重复使用 思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次…...
使用PaddleNLP UIE模型提取上市公司PDF公告关键信息
项目地址:使用PaddleNLP UIE模型抽取PDF版上市公司公告 - 飞桨AI Studio星河社区 (baidu.com) 背景介绍 本项目将演示如何通过PDFPlumber库和PaddleNLP UIE模型,抽取公告中的相关信息。本次任务的PDF内容是破产清算的相关公告,目标是获取受理…...
软件工程师,OpenAI Sora驾到,快来围观
概述 近期,OpenAI在其官方网站上公布了Sora文生视频模型的详细信息,展示了其令人印象深刻的能力,包括根据文本输入快速生成长达一分钟的高清视频。Sora的强大之处在于其能够根据文本描述,生成长达60秒的视频,其中包含&…...
【Linux 04】编辑器 vim 详细介绍
文章目录 🌈 Ⅰ 基本概念🌈 Ⅱ 基本操作1. 进入 / 退出 vim2. vim 模式切换 🌈 Ⅲ 命令模式1. 光标的移动2. 复制与粘贴3. 剪切与删除4. 撤销与恢复 🌈 Ⅳ 底行模式1. 保存文件2. 查找字符3. 退出文件4. 替换内容5. 显示行号6. 外…...
KMP算法详解
1. 问题引入 链接:leetcode_28 题目:s1字符串是否包含s2字符串,如果包含返回s1中包含s2的最左开头位置,不包含返回-1 暴力方法就是s1的每个位置都做开头,然后去匹配s2整体,时间复杂度O(n*m) KMP算法可以…...
ubuntu22.04@laptop OpenCV Get Started: 013_contour_detection
ubuntu22.04laptop OpenCV Get Started: 013_contour_detection 1. 源由2. 应用Demo2.1 C应用Demo2.2 Python应用Demo 3. contour_approx应用3.1 读取图像并将其转换为灰度格式3.2 应用二进制阈值过滤算法3.3 查找对象轮廓3.4 绘制对象轮廓3.5 效果3.6 CHAIN_APPROX_SIMPLE v.s…...
[ai笔记5] 个人AI资讯助手实战
欢迎来到文思源想的ai空间,这是技术老兵重学ai以及成长思考的第5篇分享,也是把ai场景化应用的第一篇实操内容! 既然要充分学习和了解ai,自然少不了要时常看看ai相关资讯,所以今天特地用字节的“扣子”做了一个ai的资讯…...
QT+OSG/osgEarth编译之八十九:osgdb_ply+Qt编译(一套代码、一套框架,跨平台编译,版本:OSG-3.6.5插件库osgdb_ply)
文章目录 一、osgdb_ply介绍二、文件分析三、pro文件四、编译实践一、osgdb_ply介绍 斯坦福三角形格式(Stanford Triangle Format)是一种用于存储三维模型数据的文件格式,也称为 PLY 格式。它最初由斯坦福大学图形实验室开发,用于存储和共享三维扫描和计算机图形数据。 P…...
机器人专题:我国机器人产业园区发展现状、问题、经验及建议
今天分享的是机器人系列深度研究报告:《机器人专题:我国机器人产业园区发展现状、问题、经验及建议》。 (报告出品方:赛迪研究院) 报告共计:26页 机器人作为推动工业化发展和数字中国建设的重要工具&…...
算法沉淀——哈希算法(leetcode真题剖析)
算法沉淀——哈希算法 01.两数之和02.判定是否互为字符重排03.存在重复元素04.存在重复元素 II05.字母异位词分组 哈希算法(Hash Algorithm)是一种将任意长度的输入(也称为消息)映射为固定长度的输出的算法。这个输出通常称为哈希…...
深入理解Redis哨兵原理
哨兵模式介绍 在深入理解Redis主从架构中Redis 的主从架构中,由于主从模式是读写分离的,如果主节点(master)挂了,那么将没有主节点来服务客户端的写操作请求,也没有主节点给从节点(slave&#…...
MySQL-存储过程(PROCEDURE)
文章目录 1. 什么是存储过程?2. 存储过程的优点3. MySQL中的变量3.1 系统变量3.2 用户自定义变量3.3 局部变量 4. 存储过程的相关语法4.1 创建存储过程(CREATE)4.2 查看存储过程(SHOW)4.3 修改存储过程(ALT…...
linux系统监控工具prometheus的安装以及监控mysql
prometheus 安装服务端客户端监控mysql prometheus浏览器查看 安装 https://prometheus.io/download/下载客户端和服务端以及需要监控的所有的包服务端 官网下载下载prometheustar -xf prometheus-2.47.2.linux-amd64.tar.gz -C /usr/local/ cd /usr/local/ mv prometheus-2.…...
初识tensorflow程序设计模式
文章目录 建立计算图tensorflow placeholdertensorflow数值运算常用的方法 tensorboard启动tensorboard的方法 建立一维与二维张量建立一维张量建立二维张量建立新的二维张量 矩阵的基本运算矩阵的加法矩阵乘法与加法 github地址https://github.com/fz861062923/TensorFlow 建…...
【QT+QGIS跨平台编译】之三十八:【GDAL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
文章目录 一、gdal介绍二、文件下载三、文件分析四、pro文件五、编译实践一、gdal介绍 GDAL(Geospatial Data Abstraction Library)是一个用于读取、写入和处理地理空间数据的开源库。它支持多种栅格和矢量地理空间数据格式,包括常见的GeoTIFF、Shapefile、NetCDF、HDF5等,…...
黑马鸿蒙教程学习1:Helloworld
今年打算粗略学习下鸿蒙开发,当作兴趣爱好,通过下华为那个鸿蒙开发认证, 发现黑马的课程不错,有视频和完整的代码和课件下载,装个devstudio就行了,建议32G内存。 今年的确是鸿蒙大爆发的一年呀,…...
蓝桥杯每日一题------背包问题(四)
前言 前面讲的都是背包的基础问题,这一节我们进行背包问题的实战,题目来源于一位朋友的询问,其实在这之前很少有题目是我自己独立做的,我一般习惯于先看题解,验证了题解提供的代码是正确的后,再去研究题解…...
OpenAI发布Sora技术报告深度解读!真的太强了!
😎 作者介绍:我是程序员洲洲,一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号:洲与AI。 🎈 本文专栏:本文收录…...
AJAX——接口文档
1 接口文档 接口文档:描述接口的文章 接口:使用AJAX和服务器通讯时,使用的URL,请求方法,以及参数 传送门:AJAX阶段接口文档 <!DOCTYPE html> <html lang"en"><head><meta c…...
leetcode hot100不同路径
本题可以采用动态规划来解决。还是按照五部曲来做 确定dp数组:dp[i][j]表示走到(i,j)有多少种路径 确定递推公式:我们这里,只有两个移动方向,比如说我移动到(i,j&#x…...
【前端工程化面试题目】webpack 的热更新原理
可以在顺便学习一下 vite 的热更新原理,请参考这篇文章。 首先有几个知识点需要明确 热更新是针对开发过程中的开发服务器的,也就是 webpack-dev-serverwebpack 的热更新不需要额外的插件,但是需要在配置文件中 devServer属性中配置&#x…...
不花一分钱,在 Mac 上跑 Windows(M1/M2 版)
这是在 MacOS M1 上体验最新 Windows11 的效果: VMware Fusion,可以运行 Windows、Linux 系统,个人使用 licence 免费 安装流程见 👉 https://zhuanlan.zhihu.com/p/452412091 从申请 Fusion licence 到下载镜像,再到…...
Attempt to call an undefined function glutInit
Attempt to call an undefined function glutInit 解决方法: 从这里下载PyOpenGL 的whl安装文件, https://drive.google.com/drive/folders/1mz7faVsrp0e6IKCQh8MyZh-BcCqEGPwx 安装命令举栗 pip install PyOpenGL-3.1.7-cp39-cp39-win_amd64.whl pi…...
AB测试最小样本量
1.AB实验过程 常见的AB实验过程,分流-->实验-->数据分析-->决策:分流:用户被随机均匀的分为不同的组实验:同一组内的用户在实验期间使用相同的策略,不同组的用户使用相同或不同的策略。数据收集:…...
在Spring中事务失效的场景
在Spring框架中,事务管理是通过AOP(面向切面编程)实现的,主要依赖于Transactional注解。然而,在某些情况下,事务可能会失效。以下是一些可能导致Spring事务失效的常见场景: 非public方法&#…...
Rust 学习笔记 - 变量声明与使用
前言 任何一门编程语言几乎都脱离不了:变量、基本类型、函数、注释、循环、条件判断,这是一门编程语言的语法基础,只有当掌握这些基础语法及概念才能更好的学习 Rust。 变量介绍 Rust 是一种强类型语言,但在声明变量时…...
windows 下跑起大模型(llama)操作笔记
原贴地址:https://testerhome.com/topics/39091 前言 国内访问 chatgpt 太麻烦了,还是本地自己搭一个比较快,也方便后续修改微调啥的。 之前 llama 刚出来的时候在 mac 上试了下,也在 windows 上用 conda 折腾过,环…...
人工智能专题:基础设施行业智能化的基础设施,自智网络双价值分析
今天分享的是人工智能系列深度研究报告:《人工智能专题:基础设施行业智能化的基础设施,自智网络双价值分析》。 (报告出品方:埃森哲) 报告共计:32页 自智网络驱动的电信产业变革 经过多年的…...
docker 编译安装redis脚本
在Docker中编译安装Redis通常不是一个常见的做法,因为Redis官方提供了预编译的Docker镜像,这些镜像包含了已经编译好的Redis二进制文件。不过,如果你有特殊需求,想要自己从源代码编译Redis并打包成Docker镜像,你可以使…...
鸿蒙开发系列教程(二十三)--List 列表操作(2)
列表样式 1、设置内容间距 在列表项之间添加间距,可以使用space参数,主轴方向 List({ space: 10 }) { … } 2、添加分隔线 分隔线用来将界面元素隔开,使单个元素更加容易识别。 startMargin和endMargin属性分别用于设置分隔线距离列表侧…...
C#根据权重抽取随机数
(游戏中一个很常见的简单功能,比如抽卡抽奖抽道具,或者一个怪物有多种攻击动作,按不同的权重随机出个攻击动作等等……) 假如有三种物品 A、B、C,对应的权重分别是A(50),…...
SORA:OpenAI最新文本驱动视频生成大模型技术报告解读
Video generation models as world simulators:作为世界模拟器的视频生成模型 1、概览2、Turning visual data into patches:将视觉数据转换为补丁3、Video compression network:视频压缩网络4、Spacetime Latent Patches:时空潜在…...
阿里云第七代云服务器ECS计算c7、通用g7和内存r7配置如何选择?
阿里云服务器配置怎么选择合适?CPU内存、公网带宽和ECS实例规格怎么选择合适?阿里云服务器网aliyunfuwuqi.com建议根据实际使用场景选择,例如企业网站后台、自建数据库、企业OA、ERP等办公系统、线下IDC直接映射、高性能计算和大游戏并发&…...
视觉slam十四讲学习笔记(六)视觉里程计 1
本文关注基于特征点方式的视觉里程计算法。将介绍什么是特征点,如何提取和匹配特征点,以及如何根据配对的特征点估计相机运动。 目录 前言 一、特征点法 1 特征点 2 ORB 特征 FAST 关键点 BRIEF 描述子 3 特征匹配 二、实践:特征提取…...
PyTorch-线性回归
已经进入大模微调的时代,但是学习pytorch,对后续学习rasa框架有一定帮助吧。 <!-- 给出一系列的点作为线性回归的数据,使用numpy来存储这些点。 --> x_train np.array([[3.3], [4.4], [5.5], [6.71], [6.93], [4.168],[9.779], [6.1…...
C++数据结构与算法——栈与队列
C第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更…...
掌上新闻随心播控,HarmonyOS SDK助力新浪新闻打造精致易用的资讯服务新体验
原生智能是HarmonyOS NEXT的核心亮点之一,依托HarmonyOS SDK丰富全面的开放能力,开发者只需通过几行代码,即可快速实现AI功能。新浪新闻作为鸿蒙原生应用开发的先行者之一,从有声资讯入手,将基于Speech Kit朗读控件上线…...
2024年危险化学品经营单位主要负责人证模拟考试题库及危险化学品经营单位主要负责人理论考试试题
题库来源:安全生产模拟考试一点通公众号小程序 2024年危险化学品经营单位主要负责人证模拟考试题库及危险化学品经营单位主要负责人理论考试试题是由安全生产模拟考试一点通提供,危险化学品经营单位主要负责人证模拟考试题库是根据危险化学品经营单位主…...
C/C++如何把指针所指向的指针设为空指针?
实践出真知,指针对于初学的友友来说,头都要大了。喵喵一直遵循在实践中学,在学习中实践,相信你也会有所得! 以下是该问题的解决方案: int** ptrPtr new int*; // 创建指向指针的指针 int* ptr new int;…...
第三节:基于 InternLM 和 LangChain 搭建你的知识库(课程笔记)
视频链接:https://www.bilibili.com/video/BV1sT4y1p71V/?vd_source3bbd0d74033e31cbca9ee35e111ed3d1 文档地址: https://github.com/InternLM/tutorial/tree/main/langchain 课程笔记: 1.仅仅包含训练时间点之前的数据,无法…...
qt-C++笔记之打印所有发生的事件
qt-C笔记之打印所有发生的事件 code review! 文章目录 qt-C笔记之打印所有发生的事件1.ChatGPT问答使用 QApplication 的 notify 方法使用 QObject 的 event 方法 2.使用 QObject 的 event 方法3.使用 QApplication 的 notify 方法 1.ChatGPT问答 在Qt C中,若要打…...
pytorch 实现线性回归(深度学习)
一 查看原始函数 初始化 %matplotlib inline import random import torch from d2l import torch as d2l 1.1 生成原始数据 def synthetic_data(w, b, num_examples):x torch.normal(0, 1, (num_examples, len(w)))y torch.matmul(x, w) bprint(x:, x)print(y:, y)y tor…...
[Doris] Doris的安装和部署 (二)
文章目录 1.安装要求1.1 Linux操作系统要求1.2 软件需求1.3 注意事项1.4 内部端口 2.集群部署2.1 操作系统安装要求2.2 下载安装包2.3 解压2.4 配置FE2.5 配置BE2.6 添加BE2.7 FE 扩容和缩容2.8 Doris 集群群起脚本 3.图形化 1.安装要求 1.1 Linux操作系统要求 1.2 软件需求 1…...
【QT+QGIS跨平台编译】之三十五:【cairo+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
文章目录 一、cairo介绍二、文件下载三、文件分析四、pro文件五、编译实践一、cairo介绍 Cairo是一个功能强大的开源2D图形库,它提供了一套跨平台的API,用于绘制矢量图形和文本。Cairo支持多种输出目标,包括屏幕、图像文件、PDF、SVG等。 Cairo的设计目标是简单易用、高效…...
MySQL(基础)
第01章_数据库概述 1. 为什么要使用数据库 持久化(persistence):把数据保存到可掉电式存储设备中以供之后使用。大多数情况下,特别是企业级应用,数据持久化意味着将内存中的数据保存到硬盘上加以”固化”,而持久化的实现过程大多…...
STM32F1 - 中断系统
Interrupt 1> 硬件框图2> NVIC 中断管理3> EXTI 中断管理3.1> EXTI与NVIC3.2> EXTI内部框图 4> 外部中断实验4.1> 实验概述4.2> 程序设计 5> 中断向量表6> 总结 1> 硬件框图 NVIC:Nested Vectored Interrupt Controller【嵌套向量…...
【Linux系统化学习】缓冲区
目录 缓冲区 一个样例 现象解释 缓冲区存在的位置 缓冲区 在刚开始学习C语言的时候我们就听过缓冲区这个名词,很是晦涩难懂;在Linux下进程退出时也包含缓冲区,因此缓冲区到底是什么?有什么作用? 让我们先从一个小…...
基于BP算法的SAR成像matlab仿真
目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1 BP算法的基本原理 4.2 BP算法的优点与局限性 5.完整工程文件 1.课题概述 基于BP算法的SAR成像。合成孔径雷达(SAR)是一种高分辨率的雷达系统,能够在各种天气和光…...
【C++ STL】你真的了解string吗?浅谈string的底层实现
文章目录 底层结构概述扩容机制浅拷贝与深拷贝插入和删除的效率浅谈VS和g的优化总结 底层结构概述 string可以帮助我们很好地管理字符串,但是你真的了解她吗?事实上,string的设计是非常复杂的,拥有上百个接口,但最常用…...
17.3.1.3 灰度
版权声明:本文为博主原创文章,转载请在显著位置标明本文出处以及作者网名,未经作者允许不得用于商业目的。 灰度的算法主要有以下三种: 1、最大值法: 原图像:颜色值color(R,G,B&a…...