刷代码随想有感(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文…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...

解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...

【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...