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

算法基础之01背包问题

01背包问题

  • 核心思想:

    • 二维数组普通写法:

      •   #include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 1010;int f[N][N];  //存 i个物品 容量不超过j 的总价值int v[N],w[N];int n,m;int main(){cin>>n>>m;for(int i =1;i<=n;i++) scanf("%d%d" , &v[i] , &w[i]);for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j] = f[i-1][j];  //不放第i个物品的情况if(j >= v[i])  //可以放的情况{  f[i][j] = max(f[i][j] , f[i-1][j-v[i]] + w[i]);  //f[i-1]是前一个的状态 +w[i] 是现在的}}}cout<<f[n][m];  //含义: 个数不超过n 容量不超过m 情况下最大价值 return 0;}
        
    • 一维数组优化版本:

      •   int main(){cin>>n>>m;for(int i =1;i<=n;i++) scanf("%d%d" , &v[i] , &w[i]);for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--)  //逆序遍历 因为原来是用i-1更新i 逆序可以保证//用j-v[i]时 还是上一层(i-1)的 因为j> j-v[i]{f[j] = max(f[j] , f[j-v[i]] + w[i]);}}cout<<f[m];return 0;}
        

相关文章:

算法基础之01背包问题

01背包问题 核心思想&#xff1a; 二维数组普通写法: #include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N 1010;int f[N][N]; //存 i个物品 容量不超过j 的总价值int v[N],w[N];int n,m;int main(){cin>>n>…...

Git的总体认知与具体实现

GIt概念 是一种分布式控制管理器 tips:敏捷开发 -> 先上线&#xff0c;后续开发再继续开发 集中式和分布式 集中式的版本控制系统每次在写代码时都需要从服务器中拉取一份下来&#xff0c;并且如果服务器丢失了&#xff0c;那么所有的就都丢失了&#xff0c;你本机客户端仅…...

Hadoop入门学习笔记——三、使用HDFS文件系统

视频课程地址&#xff1a;https://www.bilibili.com/video/BV1WY4y197g7 课程资料链接&#xff1a;https://pan.baidu.com/s/15KpnWeKpvExpKmOC8xjmtQ?pwd5ay8 Hadoop入门学习笔记&#xff08;汇总&#xff09; 目录 三、使用HDFS文件系统3.1. 使用命令操作HDFS文件系统3.1.…...

JavaWeb—html, css, javascript, dom,xml, tomcatservlet

文章目录 快捷键HTML**常用特殊字符替代:****标题****超链接标签****无序列表、有序列表****无序列表**:ul/li 基本语法**有序列表ol/li:****图像标签(img)**** 表格(table)标签****表格标签-跨行跨列表格****form(表单)标签介绍****表单form提交注意事项**div 标签p 标签sp…...

LangChain 31 模块复用Prompt templates 提示词模板

LangChain系列文章 LangChain 实现给动物取名字&#xff0c;LangChain 2模块化prompt template并用streamlit生成网站 实现给动物取名字LangChain 3使用Agent访问Wikipedia和llm-math计算狗的平均年龄LangChain 4用向量数据库Faiss存储&#xff0c;读取YouTube的视频文本搜索I…...

深入理解 Git 分支管理:提升团队协作与开发效率

目录 前言1 什么是分支2 分支的好处2.1 并行开发的支持2.2 独立性与隔离性2.3 灵活的版本控制2.4 提高安全性和代码质量2.5 项目历史的清晰记录 3 Git 分支操作命令3.1 git branch -v3.2 git branch 分支名称3.3 git checkout 分支名称3.4 git merge 分支名称3.5 git rebase 分…...

WPF StackPanel

StackPanel是一个控件容器&#xff0c;它按照一个方向&#xff08;水平或垂直&#xff09;堆叠子元素&#xff0c;使得它们沿一个轴线对齐。你可以在StackPanel中放置其他控件&#xff0c;如按钮、标签、文本框、图片等等。这些控件的排列方式由StackPanel按照指定的方向自动确…...

由正规表达式构造DFA,以及DFA的相关化简

目录 1.由正规式到DFA 首先讲如何从正规式到NFA 如何从NFA到DFA 2.DFA的化简 3.DFA和NFA的区别 1.由正规式到DFA 正规式--->NFA---->DFA 首先讲如何从正规式到NFA 转换规则: 例题1&#xff1a;这里圆圈里面的命名是随意的&#xff0c;只要能区别开就可以了 如何…...

模式识别与机器学习(九):Adaboost

1.原理 AdaBoost是Adaptive Boosting&#xff08;自适应增强&#xff09;的缩写&#xff0c;它的自适应在于&#xff1a;被前一个基本分类器误分类的样本的权值会增大&#xff0c;而正确分类的样本的权值会减小&#xff0c;并再次用来训练下一个基本分类器。同时&#xff0c;在…...

【JAVA】分布式链路追踪技术概论

目录 1.概述 2.基于日志的实现 2.1.实现思想 2.2.sleuth 2.2.可视化 3.基于agent的实现 4.联系作者 1.概述 当采用分布式架构后&#xff0c;一次请求会在多个服务之间流转&#xff0c;组成单次调用链的服务往往都分散在不同的服务器上。这就会带来一个问题&#xff1a;…...

ZooKeeper 使用介绍和原理详解

目录 1. 介绍 重要性 应用场景 2. ZooKeeper 架构 服务角色 数据模型 工作原理 3. 安装和配置 下载 ZooKeeper 安装和配置 启动 ZooKeeper 验证和管理 停止和关闭 4. ZooKeeper 数据模型 数据结构和层次命名空间&#xff1a; 节点类型和 Watcher 机制&#xff…...

模式识别与机器学习(八):决策树

1.原理 决策树&#xff08;Decision Tree&#xff09;&#xff0c;它是一种以树形数据结构来展示决策规则和分类结果的模型&#xff0c;作为一种归纳学习算法&#xff0c;其重点是将看似无序、杂乱的已知数据&#xff0c;通过某种技术手段将它们转化成可以预测未知数据的树状模…...

Pinely Round 3 (Div. 1 + Div. 2)(A~D)(有意思的题)

A - Distinct Buttons 题意&#xff1a; 思路&#xff1a;模拟从&#xff08;0,0&#xff09;到每个位置需要哪些操作&#xff0c;如果总共需要4种操作就输出NO。 // Problem: A. Distinct Buttons // Contest: Codeforces - Pinely Round 3 (Div. 1 Div. 2) // URL: https…...

在Linux下探索MinIO存储服务如何远程上传文件

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;网络奇遇记、Cpolar杂谈 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 创建Buckets和Access Keys二. Linux 安装Cpolar三. 创建连接MinIO服务公网地…...

持续集成交付CICD:Linux 部署 Jira 9.12.1

目录 一、实验 1.环境 2.K8S master节点部署Jira 3.Jira 初始化设置 4.Jira 使用 一、实验 1.环境 &#xff08;1&#xff09;主机 表1 主机 主机架构版本IP备注master1K8S master节点1.20.6192.168.204.180 jenkins slave &#xff08;从节点&#xff09; jira9.12.1…...

Linux命令-查看内存、GC情况及jmap 用法

查看进程占用内存、CPU使用情况 1、查看进程 #jps 查看所有java进程 #top 查看cpu占用高进程 输入m &#xff1a;根据内存排序 topMem: 16333644k total, 9472968k used, 6860676k free, 165616k buffers Swap: 0k total, 0k used, 0k free, 6…...

nginx安装letsencrypt证书

1.安装推荐安装letsencrypt证书的客户端工具 官方推荐通过cerbot客户端安装letsencrypt 官方推荐使用snap客户端安装cerbot客户端 apt install snapd snap install --classic certbot 建立certbot软链接&#xff1a;ln -s /snap/bin/certbot /usr/bin/certbot 2.开始安装letse…...

docker笔记1-安装与基础命令

docker的用途&#xff1a; 可以把应用程序代码及运行依赖环境打包成镜像&#xff0c;作为交付介质&#xff0c;在各种环境部署。可以将镜像&#xff08;image&#xff09;启动成容器&#xff08;container&#xff09;&#xff0c;并提供多容器的生命周期进行管理&#xff08;…...

VSCode软件与SCL编程

原创 NingChao NCLib 博途工控人平时在哪里技术交流博途工控人社群 VSCode简称VSC&#xff0c;是Visual studio code的缩写&#xff0c;是由微软开发的跨平台的轻量级编辑器&#xff0c;支持几乎所有主流的开发语言的语法高亮、代码智能补全、插件扩展、代码对比等&#xff0c…...

Opencv中的滤波器

一副图像通过滤波器得到另一张图像&#xff0c;其中滤波器又称为卷积核&#xff0c;滤波的过程称之为卷积。 这就是一个卷积的过程&#xff0c;通过一个卷积核得到另一张图片&#xff0c;明显发现新的到的图片边缘部分更加清晰了&#xff08;锐化&#xff09;。 上图就是一个卷…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

Axure零基础跟我学:展开与收回

亲爱的小伙伴,如有帮助请订阅专栏!跟着老师每课一练,系统学习Axure交互设计课程! Axure产品经理精品视频课https://edu.csdn.net/course/detail/40420 课程主题:Axure菜单展开与收回 课程视频:...

OpenGL-什么是软OpenGL/软渲染/软光栅?

‌软OpenGL&#xff08;Software OpenGL&#xff09;‌或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式&#xff08;包括几何处理、光栅化、着色等&#xff09;&#xff0c;不依赖GPU硬件加速。这种模式通常性能较低&#xff0c;但兼容性极强&#xff0c;常用于不支持硬件加速…...

数据挖掘是什么?数据挖掘技术有哪些?

目录 一、数据挖掘是什么 二、常见的数据挖掘技术 1. 关联规则挖掘 2. 分类算法 3. 聚类分析 4. 回归分析 三、数据挖掘的应用领域 1. 商业领域 2. 医疗领域 3. 金融领域 4. 其他领域 四、数据挖掘面临的挑战和未来趋势 1. 面临的挑战 2. 未来趋势 五、总结 数据…...

PLC入门【4】基本指令2(SET RST)

04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C)&#xff0c;从 文件 - 主画面&#xff0c;“B: 让我们学习基本的”- “B-3.控制优先程序”。 点击“梯形图编辑”…...

java+webstock

maven依赖 <dependency><groupId>org.java-websocket</groupId><artifactId>Java-WebSocket</artifactId><version>1.3.5</version></dependency><dependency><groupId>org.apache.tomcat.websocket</groupId&…...