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

代码随想录训练营第35天|逆序背包

46. 携带研究材料 

#include <iostream>
#include <vector>
using namespace std;
int main(){int m,n;cin>>m>>n;vector<int> weights(m,0), values(m,0),dp(n+1,0);for(int i=0; i<m; i++){cin>>weights[i];}for(int i=0; i<m; i++){cin>>values[i];}for(int j=0; j<m; j++){for(int i=n;i>=weights[j];i--){dp[i]=max(dp[i],dp[i-weights[j]]+values[j]);}}cout<<dp[n]<<endl;return 0;
}

经典的01背包问题,dp[i]表示容量为i的背包所能装载的最大价值。

状态转移方程:dp[i]=max(dp[i],dp[i-weights[j]]+values[j]);

用不同的物品刷新"滚动数组",每一个新的物品会占据空间weights[j],并带来价值values[j],所以得到新的价值:dp[i-weights[j]]+values[j], dp[i]累计所有可能的最大值。

另外一个细节,背包容量需要逆序遍历,这样对推过程中利用的dp[i-weights[j]]均是不考虑values[j]的最优解,也即每个物品只能使用一次。反之,如果正序遍历,大容量的dp由小容量的dp计算而来,都会计入values[j],这样一个物品就会被使用多次,成为完全背包问题。

416. 分割等和子集

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=accumulate(nums.begin(),nums.end(),0);if(sum%2==1)return false;int target=sum/2;vector<int> dp(target+1,0);for(auto& num:nums){for(int i=target; i>=num; i--){dp[i]=max(dp[i],dp[i-num]+num);}}return dp[target]==target;}
};

转化为背包问题:重量为nums的石头,放入target容量的背包中,求可放入的最大重量(价值=重量)。

5. 最长回文子串

class Solution {
public:int get_length(string& s, int left, int right){while(left>=0&&right<s.length()&&s[left]==s[right]){left--;right++;};return right-left+1-2;}string longestPalindrome(string s) {if(s.length()<2)return s;int max_len=INT_MIN,start;for(int i=0; i<s.length()-1; i++){int l1=get_length(s,i,i);int l2=get_length(s,i,i+1);if(l1>max_len){max_len=l1;start=i-(max_len-1)/2;}if(l2>max_len){max_len=l2;start=i+1-max_len/2;}}return s.substr(start,max_len);}
};

贪心解法,从中心向两边扩散,得到回文长度。遍历所有可能的中心,累计最大值。

相关文章:

代码随想录训练营第35天|逆序背包

46. 携带研究材料 #include <iostream> #include <vector> using namespace std; int main(){int m,n;cin>>m>>n;vector<int> weights(m,0), values(m,0),dp(n1,0);for(int i0; i<m; i){cin>>weights[i];}for(int i0; i<m; i){cin…...

Centos7环境下Hive的安装

Centos7环境下Hive的安装 前言一、安装Hive1.1 下载并解压1.2 配置环境变量1.3 修改配置1. hive-env.sh2. hive-site.xml 1.4 拷贝数据库驱动1.5 初始化元数据库报错 1.6 安装MySQL1.7 启动 二、HiveServer2/beeline2.1 修改Hadoop配置2.2 修改Hive配置2.2 启动hiveserver22.3 …...

??Ansible——ad-hoc

文章目录 一、ad-hoc介绍二、ad-hoc的使用1、语法2、ad-hoc常用模块1&#xff09;shell模块2&#xff09;command模块3&#xff09;script模块4&#xff09;file模块5&#xff09;copy模块6&#xff09;yum模块7&#xff09;yum-repository模块8&#xff09;service模块9&#…...

清理Go/Rust编译时产生的缓存

Go Mac 1T的磁盘频频空间高级&#xff0c;发现是/Users/yourname/Library/Caches/go-build 目录占用了大量空间。 此目录保存来自 Go 构建系统的缓存构建工件。 如果目录太大&#xff0c;请运行go clean -cache。 运行go clean -fuzzcache以删除模糊缓存。 当时直接手工清理了…...

【linux】 ls命令

ls 命令是 Linux 和 Unix 系统中用于列出目录内容的命令。它显示指定目录下的文件和子目录列表。如果不指定目录&#xff0c;ls 默认显示当前目录下的内容。 基本用法 ls [选项] [文件或目录...] 无选项&#xff1a;简单地列出当前目录下的文件和目录。文件或目录&#xff1…...

STM32的寄存器深度解析

目录 一、STM32 寄存器概述 二、寄存器的定义与作用 三、寄存器分类 1.内核寄存器 2.外设寄存器 四、重要寄存器详解 1.GPIO 相关寄存器 2.定时器相关寄存器 3.中断相关寄存器 4.RCC 相关寄存器 五、寄存器操作方法 1.直接操作寄存器 2.使用库函数操作寄存器 六…...

win11 运行vmware workstation 虚拟机很卡,解决办法

本身win11的hyper V和vmare workstation有兼容性问题&#xff0c;正常来说&#xff0c;不能二者共存 需要在win11上流畅运行vmare虚拟机&#xff0c;需要在win11用管理员权限打开power shell 然后在里面运行命令: bcdedit /set hypervisorlaunchtype off powercfg /powerthr…...

C语言 | Leetcode C语言题解之第404题左叶子之和

题目&#xff1a; 题解&#xff1a; bool isLeafNode(struct TreeNode *node) {return !node->left && !node->right; }int sumOfLeftLeaves(struct TreeNode *root) {if (!root) {return 0;}struct TreeNode **q malloc(sizeof(struct TreeNode *) * 2001);in…...

jeesite支持db2数据库初始化sql

点击下载&#xff1a;jeesite5.8.1-db2-sql.rar 提取码: yqev...

微信小程序页面制作——婚礼邀请函(含代码)

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

股票量化接口api,国内股票期权怎么交易

炒股自动化&#xff1a;申请官方API接口&#xff0c;散户也可以 python炒股自动化&#xff08;0&#xff09;&#xff0c;申请券商API接口 python炒股自动化&#xff08;1&#xff09;&#xff0c;量化交易接口区别 Python炒股自动化&#xff08;2&#xff09;&#xff1a;获取…...

Spring解决循环依赖的原理

通过将自己注入自己&#xff0c;使用代理对象调用add方法解决了事务失效问题&#xff0c;但是这样不会产生循环依赖吗&#xff1f; 在OrdersCreateServiceImpl 中注入的是OrdersCreateServiceImpl 的代理对象&#xff0c;并不是OrdersCreateServiceImpl 本身实例&#xff0c;构…...

Openal o1初探

9 月 13 日&#xff0c;OpenAI 正式公开一系列全新 AI 大模型&#xff0c;传说的“草莓”终于上线&#xff0c;但是正式命名不叫“草莓”&#xff0c;而是o1。 一、为什么叫o1 为什么取名叫o1&#xff0c;OpenAI是这么说的&#xff1a; For complex reasoning tasks this is…...

基于python+django+vue的学生成绩管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于协同过滤pythondjangovue…...

mimd 公平收敛在相图中的细节

aimd 的收敛已经说腻了&#xff0c;我曾经画了好几次相图。有朋友希望我能画一个 mimd 相图&#xff0c;我就再画一个稍微详细的。 下面相图收敛到稳定点的前提异步 mimd&#xff1a; 之所以要异步&#xff0c;举个例子&#xff0c;在执行 gx 时&#xff0c;要确保 y 已经执…...

爬虫--翻页tips

免责声明&#xff1a;本文仅做分享&#xff01; 伪线程 from DrissionPage import ChromiumPage import timepage ChromiumPage() page.get("https://you.ctrip.com/sight/taian746.html") # 初始化 第0页 index_page 0# 翻页点击函数 sleep def page_turn():page…...

论文内容分类与检测系统源码分享

论文内容分类与检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Comput…...

【MySQL】将表导出CSV(可以使用excel打开)

1、准备工作 查看数据库&#xff1a; show databases;切换数据库&#xff1a; use 数据库名;查看表名字 show tables;2、单个表导出 需要替换导出csv文件目录和表名 SELECT * INTO OUTFILE 目录/文件名.csv FIELDS TERMINATED BY , ENCLOSED BY " LINES TERMINATED …...

通用四期ARM架构银河麒麟桌面操作系统V10【安装、配置FTP服务端】

一、操作环境 服务端&#xff1a;银河麒麟桌面操作系统V10SP1 &#xff08;服务端包链接&#xff1a;https://download.csdn.net/download/AirIT/89747026&#xff09; 客户端&#xff1a;银河麒麟桌面操作系统V10SP1 &#xff08;客户端包链接&#xff1a;https://downloa…...

梧桐数据库(WuTongDB):RBO(Rule-Based Optimizer)优化器简介

RBO&#xff08;Rule-Based Optimizer&#xff0c;基于规则的优化器&#xff09; 是一种早期的数据库查询优化方法&#xff0c;它通过预定义的一组规则来决定查询的执行计划&#xff0c;而不是像 CBO&#xff08;Cost-Based Optimizer&#xff0c;基于成本的优化器&#xff09;…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

Linux-进程间的通信

1、IPC&#xff1a; Inter Process Communication&#xff08;进程间通信&#xff09;&#xff1a; 由于每个进程在操作系统中有独立的地址空间&#xff0c;它们不能像线程那样直接访问彼此的内存&#xff0c;所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...