当前位置: 首页 > 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;。 上图就是一个卷…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...