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

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...

「Java基本语法」变量的使用

变量定义 变量是程序中存储数据的容器&#xff0c;用于保存可变的数据值。在Java中&#xff0c;变量必须先声明后使用&#xff0c;声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例&#xff1a;声明与初始化 public class VariableDemo {publi…...