刷代码随想有感(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数组
题干: 代码: #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是一款开源的容器管理平台,它提供了一个直观易用的…...
SqlSugar 集成
1 关于 SqlSugar SqlSugar 是 .NET/C# 平台非常优秀的 ORM 框架,目前 Nuget 总下载突破 700K,Github 关注量也高达 3.2K,是目前当之无愧的国产优秀 ORM 框架之一。 SqlSugar 官方地址:果糖网 ( 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仿真实现,仿真输出算法的优化收敛曲线,对比不同的适应度函数。 2.测试软件版本以及运行结果展示…...
Web前端项目-交互式3D魔方【附源码】
交互式3D魔方 3D魔方游戏是一款基于网页技术的三维魔方游戏。它利用HTML、CSS和JavaScript前端技术来实现3D效果,并在网页上呈现出逼真的魔方操作体验。 运行效果: 一:index.html <!DOCTYPE html> <html><head><…...
视频格式转换avi格式怎么弄?分享视频转换方法
视频格式转换avi格式怎么弄?AVI作为一种广泛支持的视频格式,能够在多种设备和播放器上顺畅播放,确保我们的视频内容能够无障碍地分享给朋友或上传至各大平台。其次,AVI格式通常具有较好的兼容性,能够避免格式转换过程中…...
UniRx 入门
Reactive X 是 Reactive Extensions 的缩写,一般简写为 Rx,最初是 LINQ 的一个扩展,由微软的团队开发,Rx 是一个编程模型,目标是提供一致的编程接口,帮助开发者更方便的处理异步数据流,支持大部…...
简单游戏制作——飞行棋
控制台初始化 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 场景选择相关 //声…...
等保一体机
等保一体机是面向等保场景推出的合规型安全防护产品。基于“一个中心,三重防护”的设计理念,通过内置全面、多样的安全能力,为政府、医疗、教育、企业等中小型客户提供快速合规、按需赋能的一站式等保合规解决方案。 等保一体机要求管理网络和…...
什么是寄存器文件(Register File)?
寄存器文件(Register File)是计算机系统中用于存储处理器操作数的小型、快速的存储单元集。它在 CPU 内部,提供极高的访问速度,通常用于存储临时数据、操作数和指令执行过程中的中间结果。 寄存器文件的组成和特点 寄存器集&…...
6月15号作业
使用手动连接,将登录框中的取消按钮使用第二中连接方式,右击转到槽,在该槽函数中,调用关闭函数 将登录按钮使用qt4版本的连接到自定义的槽函数中,在槽函数中判断ui界面上输入的账号是否为"admin"࿰…...
零基础入门学用Arduino 第三部分(三)
重要的内容写在前面: 该系列是以up主太极创客的零基础入门学用Arduino教程为基础制作的学习笔记。个人把这个教程学完之后,整体感觉是很好的,如果有条件的可以先学习一些相关课程,学起来会更加轻松,相关课程有数字电路…...
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 你正在玩策略卡牌杀戮尖塔游戏,轮到你出牌,手里N张攻击卡,每张都需要花金币coust[i]和获得伤害dmager[i]。 最多花3金币能造成的最大伤害是多少? class Solution{public int calc(int[] cost, int[] dmager, N){int[][] db …...
Kubernetes (K8s) 和 Spring Cloud 的区别
Kubernetes (K8s) 和 Spring Cloud 是两种常用的云原生技术,它们在微服务架构和云计算领域中扮演着重要的角色。尽管两者都有助于开发和部署微服务,但它们的功能和目标存在显著差异。本文将详细讨论 Kubernetes 和 Spring Cloud 的区别,从它们…...
定个小目标之刷LeetCode热题(21)
这是道技巧题,利用了 (num - 1)% n 计算下标的形式来将数组元素与数组索引产生映射关系,代码如下,可以看下注释 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 开启钱包抱错,看下钱包信息 SQL> select * from v$encryption_wallet;WRL_TYPE -------------------- WRL_PARAMETER -------------------------------------------------------------------------------- STATUS ------…...
【麒麟虚拟机】NetworkManager没有运行
麒麟V10 建linux麒麟虚拟机,发现,网络没有配置 提示,NetworkManager没有运行。编辑联接也不能配置 解决方法,在终端输入命令: sudo systemctl start NetworkManager 启动以后,编辑连接选自动以太网&…...
vue之一键部署的shell脚本和它的点.bat文件、海螺AI、ChatGPT
MENU 前言vite.config.ts的配置deploy文件夹的其他内容remote.shpwd.txtdeploy.bat 前言 1、在src同级新建deploy.bat文件; 2、在src同级新建deploy文件夹,文件夹中新建pwd.txt和remote.sh文件; 3、配置好后,直接双击deploy.bat文…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
node.js的初步学习
那什么是node.js呢? 和JavaScript又是什么关系呢? node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说, 需要在node.js的环境上进行当JavaScript作为前端开发语言来说,需要在浏览器的环境上进行 Node.js 可…...
Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...
