当前位置: 首页 > news >正文

【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(fi1,j,fi1,jw+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=fi1,jfi1,jw+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(fi1,j,fi1,jw+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背包一般分为两种&#xff0c;不妨叫做价值01背包和判断01背包。 价值01背包 01背包问题是这样的一类问题&#xff1a;给定一个背包的容量 m m m 和 n n n 个物品&#xff0c;每个物品有重量 w w w 和价值 v v v&#xff0c;求不超过背…...

50、PHP 实现选择排序

题目&#xff1a; PHP 实现选择排序 描述&#xff1a; n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果&#xff1a;(1)初始状态&#xff1a;无序区为R[1…n]&#xff0c;有序区为空。(2)第1趟排序在无序区R[1…n]中选出关键字最小的记录R[k]&#xff0c;将…...

17.延迟队列

介绍 延迟队列&#xff0c;队列内部是有序的&#xff0c;延迟队列中的元素是希望在指定时间到了以后或之前取出和处理。 死信队列中&#xff0c;消息TTL过期的情况其实就是延迟队列。 使用场景 1.订单在十分钟内未支付则自动取消。 2.新创建的店铺&#xff0c;如果十天内没…...

KCache-go本地缓存,支持本地缓存过期、缓存过期自维护机制。

GitHub - kocor01/kcache: go 本地缓存解决方案&#xff0c;支持本地缓存过期、缓存过期自维护机制。 最近系统并发很高&#xff0c;单接口10W的 QPS&#xff0c;对 redis 压力很大&#xff0c;大量的热KEY导致 redis 分片CPU资源经常告警。计划用 go 本地缓存缓解 redis 的压…...

斯坦福UE4 C++课学习补充 14:UMG-优化血量条

文章目录 一、优化执行效率二、简单脉冲动画 一、优化执行效率 绑定事件需要每一帧检查绑定对象是否有变化&#xff0c;势必造成CPU资源的浪费&#xff0c;因此优化执行效率的思路是&#xff1a;UI组件不再自行每帧查询血量&#xff0c;而是让血量自己在发生变化的同时通知UI进…...

在生信分析中大家需要特别注意的事情​

在生信分析中大家需要特别注意的事情 标准的软件使用和数据分析流程 1. 先看我的b站教学视频 2. 先从我的百度网盘把演示数据集下载下来&#xff0c;先把要运行的模块的演示数据集先运行一遍 3. 前两步都做完了&#xff0c;演示数据集也运行成功了&#xff0c;并且知道了软件…...

Java工厂模式详解:方法工厂模式与抽象工厂模式

Java工厂模式详解&#xff1a;方法工厂模式与抽象工厂模式 一、引言 在Java开发中&#xff0c;设计模式是解决常见软件设计问题的一种有效方式。工厂模式作为创建型设计模式的一种&#xff0c;提供了灵活的对象创建机制&#xff0c;有助于降低代码的耦合度&#xff0c;提高系…...

springSecurity学习之springSecurity用户单设备登录

用户只能单设备登录 有时候在同一个系统中&#xff0c;只允许一个用户在一个设备登录。 之前的登陆者被顶掉 将最大会话数设置为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 策略梯度方法&#xff08;Policy Gradient&#xff09;Policy Gradient 的目标函数目标函数 1目标函数 2两种目标函数的同一性 Policy Gradient 目标函数的…...

前端Long类型精度丢失:后端处理策略

文章目录 精度丢失的具体原因解决方法1. 使用 JsonSerialize 和 ToStringSerializer2. 使用 JsonFormat 注解3. 全局配置解决方案 结论 开发商城管理系统的品牌管理界面时&#xff0c;发现一个问题&#xff0c;接口返回品牌Id和页面展示的品牌Id不一致&#xff0c;如接口返回的…...

C++ | Leetcode C++题解之第300题最长递增子序列

题目&#xff1a; 题解&#xff1a; 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、编译 代码下载&#xff1a; DPDK 下载版本&#xff1a;DPDK 19.08.2 export RTE_SDK/root/dpdk-stable-19.08.2/ export RTE_TARGETx86_64-native-li…...

【计算机网络】OSPF单区域实验

一&#xff1a;实验目的 1&#xff1a;掌握在路由器上配置OSPF单区域。 2&#xff1a;学习OSPF协议的原理&#xff0c;及其网络拓扑结构改变后的变化。 二&#xff1a;实验仪器设备及软件 硬件&#xff1a;RCMS交换机、网线、内网网卡接口、Windows 2019操作系统的计算机等。…...

Java聚合快递小程序对接云洋系统程序app源码

​一场物流效率的革命 引言&#xff1a;物流新时代的序章 在数字化浪潮席卷各行各业的今天&#xff0c;物流行业也迎来了前所未有的变革。为了进一步提升物流效率&#xff0c;优化用户体验&#xff0c;聚合快递系统与云洋系统小程序的对接成为了行业内外关注的焦点。这一创新…...

【React】详解组件通信:从基础到进阶的全面指南

文章目录 一、父组件向子组件传递数据1. 基本概念2. 示例代码3. 详解定义子组件 Son定义父组件 App导出父组件 App数据流props 的内容 二、子组件向父组件传递数据1. 基本概念2. 示例代码3. 详解引入React库和useState钩子定义子组件 Son定义父组件 App导出父组件 App数据流 三…...

【vluhub】zabbix漏洞

介绍&#xff1a; zabbix是对服务器资源状态例如、内存空间、CPU、程序运行状态进行检测、设置预警值、短信设置等功能等一款开源工具。配置不当存在未授权,SQL注入漏洞 弱口令 nameadmin&passwordzabbix nameguest&password POST /index.php HTTP/1.1 Host: 192.1…...

openGauss触发器详解

openGauss 是一款开源关系型数据库管理系统&#xff0c;广泛应用于企业级应用中。随着数据量的增长和业务逻辑的复杂化&#xff0c;数据库管理和操作的自动化需求越来越高。触发器&#xff08;Triggers&#xff09;作为数据库中重要的编程工具&#xff0c;能够极大地简化复杂操…...

抄作业-跟着《React通关秘籍》捣鼓React-playground-上集

文章目录 前言1. 搭建react 开发环境2、react hooks 知识3. 目标&#xff1a;跟着小册实现 react-playground3.1 整体布局初始化项目使用Alloment 来实现左右分屏的拖拉功能 3.2 代码编辑器Monaco Editor 3.3 实现了多文件的切换用 useContext 来共享数据。优化 tab的样式&…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...