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

刷代码随想有感(104):动态规划——01背包问题/二维dp数组

题干:

代码:

#include<bits/stdc++.h>
using namespace std;
int n,bagweight;
void solve(){vector<int>weight(n, 0);vector<int>value(n, 0);for(int i = 0; i < n; i++){cin>>weight[i];}for(int j = 0; j < n; j++){cin>>value[j];}vector<vector<int>>dp(weight.size(), vector<int>(bagweight + 1, 0));//初始化1for(int j = weight[0]; j <= bagweight; j++){dp[0][j] = value[0];//初始化2,初始化第一横行}for(int i = 1; i < weight.size(); i++){for(int j = 0; j <= bagweight; j++){if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], (dp[i - 1][j - weight[i]] + value[i]));}}cout<<dp[weight.size() - 1][bagweight]<<endl;
}
int main(){while(cin>>n>>bagweight){solve();}
}

1.定义dp[i][j]:对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

        1.1.定义dp数组:

vector<vector<int>>dp(weight.size(), vector<int>(bagweight + 1, 0));

  由于weight数组已经包含了0所以不需要加一,而bagweight需要把0也加上,所以加一。

2.递推公式:有两个方向推出来dp[i][j],

  • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)
  • 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.遍历顺序:先是物品后是背包:

for(int i = 1; i < weight.size(); i++){for(int j = 0; j <= bagweight; j++){if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], (dp[i - 1][j - weight[i]] + value[i]));}}

4.所求的目标结果:dp[weight.size() - 1][bagweight]

最终结果是dp[2][4],也即:i = weight数组长度减一,j = 包的最大容量。

相关文章:

刷代码随想有感(104):动态规划——01背包问题/二维dp数组

题干&#xff1a; 代码&#xff1a; #include<bits/stdc.h> using namespace std; int n,bagweight; void solve(){vector<int>weight(n, 0);vector<int>value(n, 0);for(int i 0; i < n; i){cin>>weight[i];}for(int j 0; j < n; j){cin>…...

Docker-Portainer可视化管理工具

Docker-Portainer可视化管理工具 文章目录 Docker-Portainer可视化管理工具介绍资源列表基础环境一、安装Docker二、配置Docker加速器三、拉取Portainer汉化版本镜像四、运行容器五、访问可视化界面 介绍 Portainer是一款开源的容器管理平台&#xff0c;它提供了一个直观易用的…...

SqlSugar 集成

1 关于 SqlSugar SqlSugar 是 .NET/C# 平台非常优秀的 ORM 框架&#xff0c;目前 Nuget 总下载突破 700K&#xff0c;Github 关注量也高达 3.2K&#xff0c;是目前当之无愧的国产优秀 ORM 框架之一。 SqlSugar 官方地址&#xff1a;果糖网 &#xff08; SqlSugar 官网 &#…...

MySQL Connector/C++ 和 MySQL Connector/ODBC 的区别

MySQL Connector/C++ 和 MySQL Connector/ODBC 是两种不同的数据库连接工具,它们各自有不同的特点和用途。以下是它们之间的一些主要区别: 1. **编程接口**: - MySQL Connector/C++ 提供了面向对象的编程接口,它是用C++编写的,提供了C++特有的类和对象来与MySQL数据库…...

Weevil-Optimizer象鼻虫优化算法的matlab仿真实现

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 Weevil-Optimizer象鼻虫优化算法的matlab仿真实现&#xff0c;仿真输出算法的优化收敛曲线&#xff0c;对比不同的适应度函数。 2.测试软件版本以及运行结果展示…...

Web前端项目-交互式3D魔方【附源码】

交互式3D魔方 ​ 3D魔方游戏是一款基于网页技术的三维魔方游戏。它利用HTML、CSS和JavaScript前端技术来实现3D效果&#xff0c;并在网页上呈现出逼真的魔方操作体验。 运行效果&#xff1a; 一&#xff1a;index.html <!DOCTYPE html> <html><head><…...

视频格式转换avi格式怎么弄?分享视频转换方法

视频格式转换avi格式怎么弄&#xff1f;AVI作为一种广泛支持的视频格式&#xff0c;能够在多种设备和播放器上顺畅播放&#xff0c;确保我们的视频内容能够无障碍地分享给朋友或上传至各大平台。其次&#xff0c;AVI格式通常具有较好的兼容性&#xff0c;能够避免格式转换过程中…...

UniRx 入门

Reactive X 是 Reactive Extensions 的缩写&#xff0c;一般简写为 Rx&#xff0c;最初是 LINQ 的一个扩展&#xff0c;由微软的团队开发&#xff0c;Rx 是一个编程模型&#xff0c;目标是提供一致的编程接口&#xff0c;帮助开发者更方便的处理异步数据流&#xff0c;支持大部…...

简单游戏制作——飞行棋

控制台初始化 int w 50; int h 50; ConsoleInit(w, h); static void ConsoleInit(int w, int h) {//基础设置//光标的隐藏Console.CursorVisible false;//舞台的大小Console.SetWindowSize(w, h);Console.SetBufferSize(w, h); } 场景选择相关 #region 场景选择相关 //声…...

等保一体机

等保一体机是面向等保场景推出的合规型安全防护产品。基于“一个中心&#xff0c;三重防护”的设计理念&#xff0c;通过内置全面、多样的安全能力&#xff0c;为政府、医疗、教育、企业等中小型客户提供快速合规、按需赋能的一站式等保合规解决方案。 等保一体机要求管理网络和…...

什么是寄存器文件(Register File)?

寄存器文件&#xff08;Register File&#xff09;是计算机系统中用于存储处理器操作数的小型、快速的存储单元集。它在 CPU 内部&#xff0c;提供极高的访问速度&#xff0c;通常用于存储临时数据、操作数和指令执行过程中的中间结果。 寄存器文件的组成和特点 寄存器集&…...

6月15号作业

使用手动连接&#xff0c;将登录框中的取消按钮使用第二中连接方式&#xff0c;右击转到槽&#xff0c;在该槽函数中&#xff0c;调用关闭函数 将登录按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff0…...

零基础入门学用Arduino 第三部分(三)

重要的内容写在前面&#xff1a; 该系列是以up主太极创客的零基础入门学用Arduino教程为基础制作的学习笔记。个人把这个教程学完之后&#xff0c;整体感觉是很好的&#xff0c;如果有条件的可以先学习一些相关课程&#xff0c;学起来会更加轻松&#xff0c;相关课程有数字电路…...

Trusty qemu + android环境搭建详细步骤

下载源码 mkdir trusty cd trusty repo init -u https://android.googlesource.com/trusty/manifest -b master repo sync -j32 编译 ./trusty/vendor/google/aosp/scripts/build.py generic-arm64 查看编译结果 ls build-root/build-generic-arm64/lk.bin 安装运行依赖 …...

杀戮尖塔游戏

Java 你正在玩策略卡牌杀戮尖塔游戏&#xff0c;轮到你出牌&#xff0c;手里N张攻击卡&#xff0c;每张都需要花金币coust[i]和获得伤害dmager[i]。 最多花3金币能造成的最大伤害是多少&#xff1f; class Solution{public int calc(int[] cost, int[] dmager, N){int[][] db …...

Kubernetes (K8s) 和 Spring Cloud 的区别

Kubernetes (K8s) 和 Spring Cloud 是两种常用的云原生技术&#xff0c;它们在微服务架构和云计算领域中扮演着重要的角色。尽管两者都有助于开发和部署微服务&#xff0c;但它们的功能和目标存在显著差异。本文将详细讨论 Kubernetes 和 Spring Cloud 的区别&#xff0c;从它们…...

定个小目标之刷LeetCode热题(21)

这是道技巧题&#xff0c;利用了 &#xff08;num - 1&#xff09;% n 计算下标的形式来将数组元素与数组索引产生映射关系&#xff0c;代码如下&#xff0c;可以看下注释 class Solution {public List<Integer> findDisappearedNumbers(int[] nums) {int n nums.lengt…...

Oracle 打开钱包 ORA-28368: cannot auto-create wallet

ORA-28368: cannot auto-create wallet 开启钱包抱错&#xff0c;看下钱包信息 SQL> select * from v$encryption_wallet;WRL_TYPE -------------------- WRL_PARAMETER -------------------------------------------------------------------------------- STATUS ------…...

【麒麟虚拟机】NetworkManager没有运行

麒麟V10 建linux麒麟虚拟机&#xff0c;发现&#xff0c;网络没有配置 提示&#xff0c;NetworkManager没有运行。编辑联接也不能配置 解决方法&#xff0c;在终端输入命令&#xff1a; sudo systemctl start NetworkManager 启动以后&#xff0c;编辑连接选自动以太网&…...

vue之一键部署的shell脚本和它的点.bat文件、海螺AI、ChatGPT

MENU 前言vite.config.ts的配置deploy文件夹的其他内容remote.shpwd.txtdeploy.bat 前言 1、在src同级新建deploy.bat文件&#xff1b; 2、在src同级新建deploy文件夹&#xff0c;文件夹中新建pwd.txt和remote.sh文件&#xff1b; 3、配置好后&#xff0c;直接双击deploy.bat文…...

在给ppt接入扣子空间(Ai)/智能体,新玩法10分钟搞定说课,公开课AI互动!

做 PPT 时&#xff0c;你是否遇到过这些痛点&#xff1a;演讲中观众突然提问&#xff0c;临时组织语言容易逻辑混乱&#xff1b;同一问题被反复询问&#xff0c;浪费演示时间&#xff1b;静态页面无法按需补充细节&#xff0c;信息传递不精准。而扣子空间&#xff08;Coze&…...

如何用RSPrompter提升遥感图像分割效果?基于SAM的实战技巧分享

如何用RSPrompter提升遥感图像分割效果&#xff1f;基于SAM的实战技巧分享 遥感图像分割一直是计算机视觉领域的难点之一。传统方法往往需要大量标注数据&#xff0c;而标注成本高昂&#xff0c;尤其是对于高分辨率遥感影像。2023年Meta发布的Segment Anything Model(SAM)展现了…...

任意偏振与圆偏振BIC光子晶体远场偏振计算:COMSOL中的直接画偏振态

任意偏振BIC&#xff0c;圆偏振BIC光子晶体远场偏振计算COMSOL直接画偏振态 最近在研究任意偏振BIC&#xff08;Bound states in the continuum&#xff09;和圆偏振BIC光子晶体的远场偏振计算&#xff0c;发现用COMSOL直接画偏振态还挺有意思的。今天就来聊聊这个&#xff0c…...

从黑盒到白盒:基于GB28181/RTSP全栈源码交付的AI视频平台OEM与低代码集成实战

引言&#xff1a;掌握核心代码&#xff0c;重塑交付价值链 对于系统集成商&#xff08;SI&#xff09;和独立软件开发商&#xff08;ISV&#xff09;而言&#xff0c;依赖厂商的“黑盒”产品无异于将命运交予他人。功能定制周期长、接口开放受限、Logo无法替换、私有协议无法打…...

阿姆智创21.5寸工控电脑一体机,硬核性能解锁工业自动化,源头工厂ODM定位解决方案

在工业4.0的浪潮下&#xff0c;SMT产线的精密化运行、MES与ESOP系统的数字化落地、自动化设备的智能化联动&#xff0c;对工业控制终端的综合性能、系统适配性和场景贴合度提出了更高要求。阿姆智创21.5寸工控电脑一体机&#xff0c;以工业级硬核性能为基底&#xff0c;以多系统…...

SYSTEM表空间自动增长却报ORA-01658?Oracle19C表空间管理的那些坑

Oracle 19C SYSTEM表空间自动增长失效的深度解析与实战指南 引言 在Oracle数据库管理中&#xff0c;SYSTEM表空间扮演着核心角色&#xff0c;它存储着数据字典、系统存储过程等关键元数据。然而&#xff0c;许多DBA在实际工作中都遇到过这样的困惑&#xff1a;明明设置了AUTOEX…...

别再拍脑袋立项了!手把手教你用华为IPD的Charter任务书,搞定产品从0到1的商业论证

从直觉到论证&#xff1a;中小企业如何用轻量级Charter打造产品商业闭环 深夜的创业咖啡馆里&#xff0c;几个技术出身的创始人正为下一个产品方向争论不休。"这个功能绝对能引爆市场&#xff01;"CTO激动地敲着桌子&#xff0c;"我见过三家竞品都没做好这个点。…...

从像素到对象:如何用HANet和SNUNet搞定遥感影像中的‘小目标’与‘不平衡’难题?

从像素到对象&#xff1a;HANet与SNUNet在遥感影像小目标检测中的实战解析 当洪水退去后的灾损评估卫星图上&#xff0c;那些被冲毁的农舍屋顶往往只占据几个像素&#xff1b;在城市违建监测中&#xff0c;新增的违章建筑可能只是高分辨率影像中的微小色块。这些"小目标&q…...

当服务器内存足够大时:为什么我建议你在CentOS 8上彻底禁用Swap?

大内存时代&#xff1a;CentOS 8禁用Swap的云原生性能优化实践 在云计算与容器化技术席卷全球的今天&#xff0c;服务器硬件配置正经历着革命性变化。128GB、256GB甚至TB级内存已成为现代服务器的标配&#xff0c;而传统Linux内存管理机制中的Swap分区在这种新硬件环境下是否还…...

终极指南:5步解决魔兽争霸III在现代Windows系统上的兼容性问题

终极指南&#xff1a;5步解决魔兽争霸III在现代Windows系统上的兼容性问题 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 还在为魔兽争霸III在Window…...