【DP】01背包
算法-01背包
前置知识
- DP
思路
01背包一般分为两种,不妨叫做价值01背包和判断01背包。
价值01背包
01背包问题是这样的一类问题:给定一个背包的容量 m m m 和 n n n 个物品,每个物品有重量 w w w 和价值 v v v,求不超过背包容量时可以装下的最大价值。
对于这类问题,我们使用DP,设 f i , j f_{i,j} fi,j 为考虑前 i i i 个物品时总重恰好为 j j j 的最大价值和。
容易得到DP方程: f i , j = max ( f i − 1 , j , f i − 1 , j − w + v ) f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w}+v) fi,j=max(fi−1,j,fi−1,j−w+v)
判断01背包
思路类似,方程变为 f i , j = f i − 1 , j ∣ f i − 1 , j − w + v f_{i,j}=f_{i-1,j}\mid f_{i-1,j-w}+v fi,j=fi−1,j∣fi−1,j−w+v 即可
算法参数
- 时间复杂度: Θ ( n m ) \Theta(nm) Θ(nm)
- 空间复杂度: Θ ( n m ) \Theta(nm) Θ(nm)
滚动优化
滚动优化是动态规划中最常见的空间优化了。
容易发现在动态转移方程中有 f i , j = max ( f i − 1 , j , f i − 1 , j − w + v ) f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w}+v) fi,j=max(fi−1,j,fi−1,j−w+v)
注意到第一维仅仅继承上一轮循环的状态,可以把这一维删掉。
我们注意到每次从前往后枚举 j j j,前面的状态已经被更新了,于是不妨倒过来循环,此时前面的数据还是上一次的结果,拿过来用即可。
算法参数
- 时间复杂度: Θ ( n m ) \Theta(nm) Θ(nm)
- 空间复杂度: Θ ( n + m ) \Theta(n+m) Θ(n+m)
实现代码
- 价值
f[0]=0;
for (int i=1;i<=n;i++)for (int j=m;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+v[i]);
- 判断
f[0]=1;
for (int i=1;i<=n;i++)for (int j=m;j>=w[i];j--)f[j]=f[j]|f[j-w[i]];
练习
- P1048
- P1049
- P1734
相关文章:
【DP】01背包
算法-01背包 前置知识 DP 思路 01背包一般分为两种,不妨叫做价值01背包和判断01背包。 价值01背包 01背包问题是这样的一类问题:给定一个背包的容量 m m m 和 n n n 个物品,每个物品有重量 w w w 和价值 v v v,求不超过背…...
50、PHP 实现选择排序
题目: PHP 实现选择排序 描述: n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:(1)初始状态:无序区为R[1…n],有序区为空。(2)第1趟排序在无序区R[1…n]中选出关键字最小的记录R[k],将…...
17.延迟队列
介绍 延迟队列,队列内部是有序的,延迟队列中的元素是希望在指定时间到了以后或之前取出和处理。 死信队列中,消息TTL过期的情况其实就是延迟队列。 使用场景 1.订单在十分钟内未支付则自动取消。 2.新创建的店铺,如果十天内没…...
KCache-go本地缓存,支持本地缓存过期、缓存过期自维护机制。
GitHub - kocor01/kcache: go 本地缓存解决方案,支持本地缓存过期、缓存过期自维护机制。 最近系统并发很高,单接口10W的 QPS,对 redis 压力很大,大量的热KEY导致 redis 分片CPU资源经常告警。计划用 go 本地缓存缓解 redis 的压…...
斯坦福UE4 C++课学习补充 14:UMG-优化血量条
文章目录 一、优化执行效率二、简单脉冲动画 一、优化执行效率 绑定事件需要每一帧检查绑定对象是否有变化,势必造成CPU资源的浪费,因此优化执行效率的思路是:UI组件不再自行每帧查询血量,而是让血量自己在发生变化的同时通知UI进…...
在生信分析中大家需要特别注意的事情
在生信分析中大家需要特别注意的事情 标准的软件使用和数据分析流程 1. 先看我的b站教学视频 2. 先从我的百度网盘把演示数据集下载下来,先把要运行的模块的演示数据集先运行一遍 3. 前两步都做完了,演示数据集也运行成功了,并且知道了软件…...
Java工厂模式详解:方法工厂模式与抽象工厂模式
Java工厂模式详解:方法工厂模式与抽象工厂模式 一、引言 在Java开发中,设计模式是解决常见软件设计问题的一种有效方式。工厂模式作为创建型设计模式的一种,提供了灵活的对象创建机制,有助于降低代码的耦合度,提高系…...
springSecurity学习之springSecurity用户单设备登录
用户只能单设备登录 有时候在同一个系统中,只允许一个用户在一个设备登录。 之前的登陆者被顶掉 将最大会话数设置为1就可以保证用户只能同时在一个设备上登录 Override protected void configure(HttpSecurity http) throws Exception {http..anyRequest().aut…...
微信小程序实现聊天界面,发送功能
.wxml <scroll-view scroll-y"true" style"height: {{windowHeight}}px;"><view wx:for"{{chatList}}" wx:for-index"index" wx:for-item"item" style"padding-top:{{index0?30:0}}rpx"><!-- 左…...
【强化学习的数学原理】课程笔记--5(值函数近似,策略梯度方法)
目录 值函数近似一个例子TD 算法的值函数近似形式Sarsa, Q-learning 的值函数近似形式Deep Q-learningexperience replay 策略梯度方法(Policy Gradient)Policy Gradient 的目标函数目标函数 1目标函数 2两种目标函数的同一性 Policy Gradient 目标函数的…...
前端Long类型精度丢失:后端处理策略
文章目录 精度丢失的具体原因解决方法1. 使用 JsonSerialize 和 ToStringSerializer2. 使用 JsonFormat 注解3. 全局配置解决方案 结论 开发商城管理系统的品牌管理界面时,发现一个问题,接口返回品牌Id和页面展示的品牌Id不一致,如接口返回的…...
C++ | Leetcode C++题解之第300题最长递增子序列
题目: 题解: class Solution { public:int lengthOfLIS(vector<int>& nums) {int len 1, n (int)nums.size();if (n 0) {return 0;}vector<int> d(n 1, 0);d[len] nums[0];for (int i 1; i < n; i) {if (nums[i] > d[len])…...
springboo 整合 redis
springBoot 整合 redis starter启动依赖。—包含自动装配类—完成相应的装配功能。 引入依赖 <!--引入了redis整合springboot 的依赖--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis&…...
dpdk编译安装以及接收udp报文(基于ubuntu)
目录 1、编译 2、设置运行环境 3、使用dpdk接收udp报文 3.1、设置发送端arp信息 3.2、测试 3.3、代码 4、其他 1、编译 代码下载: DPDK 下载版本:DPDK 19.08.2 export RTE_SDK/root/dpdk-stable-19.08.2/ export RTE_TARGETx86_64-native-li…...
【计算机网络】OSPF单区域实验
一:实验目的 1:掌握在路由器上配置OSPF单区域。 2:学习OSPF协议的原理,及其网络拓扑结构改变后的变化。 二:实验仪器设备及软件 硬件:RCMS交换机、网线、内网网卡接口、Windows 2019操作系统的计算机等。…...
Java聚合快递小程序对接云洋系统程序app源码
一场物流效率的革命 引言:物流新时代的序章 在数字化浪潮席卷各行各业的今天,物流行业也迎来了前所未有的变革。为了进一步提升物流效率,优化用户体验,聚合快递系统与云洋系统小程序的对接成为了行业内外关注的焦点。这一创新…...
【React】详解组件通信:从基础到进阶的全面指南
文章目录 一、父组件向子组件传递数据1. 基本概念2. 示例代码3. 详解定义子组件 Son定义父组件 App导出父组件 App数据流props 的内容 二、子组件向父组件传递数据1. 基本概念2. 示例代码3. 详解引入React库和useState钩子定义子组件 Son定义父组件 App导出父组件 App数据流 三…...
【vluhub】zabbix漏洞
介绍: zabbix是对服务器资源状态例如、内存空间、CPU、程序运行状态进行检测、设置预警值、短信设置等功能等一款开源工具。配置不当存在未授权,SQL注入漏洞 弱口令 nameadmin&passwordzabbix nameguest&password POST /index.php HTTP/1.1 Host: 192.1…...
openGauss触发器详解
openGauss 是一款开源关系型数据库管理系统,广泛应用于企业级应用中。随着数据量的增长和业务逻辑的复杂化,数据库管理和操作的自动化需求越来越高。触发器(Triggers)作为数据库中重要的编程工具,能够极大地简化复杂操…...
抄作业-跟着《React通关秘籍》捣鼓React-playground-上集
文章目录 前言1. 搭建react 开发环境2、react hooks 知识3. 目标:跟着小册实现 react-playground3.1 整体布局初始化项目使用Alloment 来实现左右分屏的拖拉功能 3.2 代码编辑器Monaco Editor 3.3 实现了多文件的切换用 useContext 来共享数据。优化 tab的样式&…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
