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

算法设计-0-1背包动态规划（C++）

news 来源：原创 2025/5/14 13:56:39

一、问题阐述

0-1 背包问题的目标是在给定背包容量 W 的情况下，从 n 个物品中选择一些物品放入背包，使得背包中物品的总价值最大。每个物品只能选择一次（即要么放入背包，要么不放入）。

二、代码

#include <iostream>
#include <vector>
using namespace std;// 动态规划解决 0-1 背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {// 创建二维 DP 表vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));// 填充 DP 表for (int i = 1; i <= n; ++i) {for (int w = 0; w <= W; ++w) {if (weights[i - 1] <= w) {// 选择第 i 个物品dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {// 不选择第 i 个物品dp[i][w] = dp[i - 1][w];}}}// 返回最大价值return dp[n][W];
}int main() {// 输入int n, W;cout << "请输入物品数量 n 和背包的最大承重 W: ";cin >> n >> W;vector<int> weights(n);vector<int> values(n);cout << "请输入每个物品的重量: ";for (int i = 0; i < n; ++i) {cin >> weights[i];}cout << "请输入每个物品的价值: ";for (int i = 0; i < n; ++i) {cin >> values[i];}// 计算最大价值int max_value = knapsack(W, weights, values, n);// 输出结果cout << "最大总价值为: " << max_value << endl;return 0;
}

三、复杂度

  • 时间复杂度：O(n * W)，其中 n 是物品数量，W 是背包容量。

  • 空间复杂度：O(n * W)，用于存储 DP 表。

四、详细阐述

代码结构

  1. 输入部分：从用户那里获取物品数量 n、背包容量 W，以及每个物品的重量和价值。

  2. 动态规划求解：使用二维 DP 表来存储子问题的解，逐步填充表格，最终得到最大价值。

  3. 输出部分：输出背包能容纳的最大价值。

动态规划表 dp

  • dp[i][w] 表示前 i 个物品在背包容量为 w 时的最大价值。

  • dp 表的大小为 (n + 1) x (W + 1)，初始化为 0。

状态转移方程

  • 对于第 i 个物品，有两种选择：

    1. 不选择第 i 个物品：最大价值为 dp[i - 1][w]。

    2. 选择第 i 个物品：最大价值为 dp[i - 1][w - weights[i - 1]] + values[i - 1]。

  • 最终选择两者中的最大值

相关文章：

算法设计-0-1背包动态规划（C++）

一、问题阐述 0-1 背包问题的目标是在给定背包容量 W 的情况下&#xff0c;从 n 个物品中选择一些物品放入背包&#xff0c;使得背包中物品的总价值最大。每个物品只能选择一次&#xff08;即要么放入背包&#xff0c;要么不放入&#xff09;。 二、代码 #include <iostr…...

编程日记 2025/5/14 13:56:39

【Java知识】使用Java实现地址逆向解析到区划信息

文章目录 1. 实现 FST1.1 定义 FST 节点1.2 定义 FST 2. 实现地址逆向查询2.1 定义区划信息2.2 构建 FST 3. 运行结果4. 代码说明5. 进一步优化6. 总结 实现一个 FST&#xff08;Finite State Transducer&#xff0c;有限状态转换器&#xff09; 并用于 地址逆向查询区划信息…...

编程日记 2025/5/13 3:19:38

单机伪分布Hadoop详细配置

目录 1. 引言2. 配置单机Hadoop2.1 下载并解压JDK1.8、Hadoop3.3.62.2 配置环境变量2.3 验证JDK、Hadoop配置 3. 伪分布Hadoop3.1 配置ssh免密码登录3.2 配置伪分布Hadoop3.2.1 修改hadoop-env.sh3.2.2 修改core-site.xml3.2.3 修改hdfs-site.xml3.2.4 修改yarn-site.xml3.2.5 …...

编程日记 2025/5/9 23:00:30

[250204] Mistral Small 3：小巧、快速、强大 | asdf 0.16.0 发布：Golang 重写带来性能飞跃

目录 Mistral AI 发布开源模型 Mistral Small 3&#xff1a;小巧、快速、强大asdf 0.16.0 版本发布&#xff1a;Golang 重写带来性能飞跃&#xff01; Mistral AI 发布开源模型 Mistral Small 3&#xff1a;小巧、快速、强大 法国人工智能初创公司 Mistral AI 发布了最新的开源…...

编程日记 2025/5/12 20:49:35

解读“大语言模型（LLM）安全性测评基准”

1. 引入 OWASP&#xff0c;全称为Open Web Application Security Project&#xff0c;即开放式Web应用程序安全项目&#xff0c;是一个致力于提高软件安全性的非营利国际组织。 由于庞大的规模和复杂的结构&#xff0c;大语言模型也存在多种安全风险&#xff0c;如prompt误导…...

编程日记 2025/5/14 12:11:39

可视化相机pose colmap形式的相机内参外参

目录 内参外参转换 可视化相机pose colmap形式的相机内参外参 内参外参转换 def visualize_cameras(cameras, images):fig plt.figure()ax fig.add_subplot(111, projection3d)for image_id, image_data in images.items():qvec image_data[qvec]tvec image_data[tvec]#…...

编程日记 2025/5/14 13:30:31

从0开始使用面对对象C语言搭建一个基于OLED的图形显示框架（基础图形库实现）

目录 基础图形库的抽象 抽象图形 抽象点 设计我们的抽象 实现我们的抽象 测试 抽象线 设计我们的抽象 实现我们的抽象 绘制垂直的和水平的线 使用Bresenham算法完成任意斜率的绘制 绘制三角形和矩形 矩形 三角形 实现 绘制圆&#xff0c;圆弧和椭圆 继续我们的…...

编程日记 2025/5/13 3:19:27

python学opencv|读取图像（五十三）原理探索：使用cv.matchTemplate()函数实现最佳图像匹配

【1】引言 前序学习进程中&#xff0c;已经探索了使用cv.matchTemplate()函数实现最佳图像匹配的技巧&#xff0c;并且成功对两个目标进行了匹配。 相关文章链接为&#xff1a;python学opencv|读取图像&#xff08;五十二&#xff09;使用cv.matchTemplate()函数实现最佳图像…...

编程日记 2025/5/13 4:47:47

4 前端前置技术（上）：AJAX技术（前端发送请求）

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 前言...

编程日记 2025/4/19 12:34:42

python的ruff简单使用

Ruff 是一个用 Rust 编写的高性能 Python 静态分析工具和代码格式化工具。它旨在提供快速的代码检查和格式化功能&#xff0c;同时支持丰富的配置选项和与现有工具的兼容性。ruff是用rust实现的python Linter&Formatter。 安装&#xff1a; conda install -c conda-forge…...

编程日记 2025/5/14 8:02:14

windows环境下如何在PyCharm中安装软件包

windows环境下如何在pyCharm中安装wxPython软件包 在windows环境中&#xff0c;安装软件包可以使用 终端 的方式&#xff0c;在IDE下方的终端中执行pip install wxPython进行安装&#xff0c;安装完毕之后&#xff0c;使用pip show wxPython检查也符合预期。 但是在代码文件中导…...

编程日记 2025/5/14 13:23:55

【LLM-agent】(task2)用llama-index搭建AI Agent

note LlamaIndex 实现 Agent 需要导入 ReActAgent 和 Function Tool&#xff0c;循环执行&#xff1a;推理、行动、观察、优化推理、重复进行。可以在 arize_phoenix 中看到 agent 的具体提示词&#xff0c;工具被装换成了提示词ReActAgent 使得业务自动向代码转换成为可能&am…...

编程日记 2025/5/14 13:53:24

Deep Crossing：深度交叉网络在推荐系统中的应用

实验和完整代码 完整代码实现和jupyter运行&#xff1a;https://github.com/Myolive-Lin/RecSys--deep-learning-recommendation-system/tree/main 引言 在机器学习和深度学习领域&#xff0c;特征工程一直是一个关键步骤&#xff0c;尤其是对于大规模的推荐系统和广告点击率预…...

编程日记 2025/5/14 13:31:37

介绍一下Mybatis的Executor执行器

Executor执行器是用来执行我们的具体的SQL操作的 有三种基本的Executor执行器&#xff1a; SimpleExecutor简单执行器 每执行一次update或select&#xff0c;就创建一个Statement对象&#xff0c;用完立刻关闭Statement对象 ReuseExecutor可重用执行器 可重复利用Statement…...

编程日记 2025/5/9 3:35:48

pthread_cond_broadcast的概念和使用案例

pthread_cond_broadcast 是 POSIX 线程&#xff08;Pthreads&#xff09;库中用于条件变量&#xff08;Condition Variable&#xff09;操作的函数&#xff0c;定义在 <pthread.h> 头文件中。它的核心作用是唤醒所有等待在某个条件变量上的线程&#xff0c;通常用于多线程…...

编程日记 2025/5/13 7:13:43

数据中心服务器对PCIe测试的需求、挑战和应用

人工智能和机器学习技术的迅猛发展&#xff0c;尤其是大语言模型&#xff08;LLM&#xff09;的兴起&#xff0c;对计算资源和数据传输速度提出了更高的要求&#xff0c;从而激发了对更高带宽解决方案的迫切需求。PCIe作为数据中心服务器间互联的主力军&#xff0c;承担着高速数…...

编程日记 2025/5/14 8:02:11

SpringBoot的配置(配置文件、加载顺序、配置原理)

文章目录 SpringBoot的配置(配置文件、加载顺序、配置原理)一、引言二、配置文件1、配置文件的类型1.1、配置文件的使用 2、多环境配置 三、加载顺序四、配置原理五、使用示例1、配置文件2、配置类3、控制器 六、总结 SpringBoot的配置(配置文件、加载顺序、配置原理) 一、引言…...

编程日记 2025/5/10 2:36:14

利用Vue和javascript分别编写一个“Hello World”的定时更新

目录 一、利用Vue编写一个“Hello World”的定时更新&#xff08;1&#xff09;vue编码在Html文件中&#xff08;2&#xff09;vue编码在js文件中 二、利用javascript编写一个“Hello World”的定时更新 一、利用Vue编写一个“Hello World”的定时更新 &#xff08;1&#xff…...

编程日记 2025/5/14 13:35:01

【免费】2007-2019年各省科技支出占一般公共预算支出的比重数据

2007-2019年各省科技支出占一般公共预算支出的比重数据 1、时间&#xff1a;2007-2019年 2、来源&#xff1a;国家统计局、统计年鉴 3、指标&#xff1a;行政区划代码、地区名称、年份、科技支出占一般公共预算支出的比重 4、范围&#xff1a;31省 5、指标解释&#xff1a…...

编程日记 2025/5/7 17:35:13

解决 LeetCode 922 题：按奇偶排序数组 II

解决 LeetCode 922 题&#xff1a;按奇偶排序数组 II 题目描述 给定一个非负整数数组 nums&#xff0c;其中一半整数是奇数&#xff0c;一半整数是偶数。要求对数组进行排序&#xff0c;以便当 nums[i] 为奇数时&#xff0c;i 也是奇数&#xff1b;当 nums[i] 为偶数时&#…...

编程日记 2025/5/13 5:38:30

【PyQt】getattr动态访问对象的属性

问题 使用qtdesigner设计好大体的软件结构&#xff0c;需要使用代码进行批量修改控件样式,self.ui.x 会被解释为访问 self.ui 中名为 x 的属性&#xff0c;而不是将 x 作为变量名来解析&#xff0c;此时需要通过字符串动态访问 self.ui 中的按钮对象 for i in range(20):x f…...

编程日记 2025/5/14 10:19:31

基于RTOS的STM32游戏机

1.游戏机的主要功能 所有游戏都来着B站JL单片机博主开源 这款游戏机具备存档与继续游戏功能&#xff0c;允许玩家在任何时候退出当前游戏并保存进度&#xff0c;以便日后随时并继续之前的冒险。不仅如此&#xff0c;游戏机还支持多任务处理&#xff0c;玩家可以在退出当前游戏…...

编程日记 2025/5/12 3:49:46

＜ 自用文儿 ＞ 下载 MaxMind GeoIP Databases 对攻击的 IP 做 地理分析

起因 两个 VPM/VPS&#xff0c;安装了 fail2ban 去拦截密码穷举攻击。每天的记录都在增长&#xff0c;以前复制屏幕输出就行&#xff0c;一屏的内容还容易粘贴出来的。昨天已经过 500 条&#xff0c;好奇 fail2ban 是如何存储这些内容的&#xff1f;就发现它在使用 SQLite3 数…...

编程日记 2025/5/7 14:07:43

kubernetes 核心技术-集群安全机制 RBAC

随着 Kubernetes 在企业级应用中的广泛采用&#xff0c;确保集群的安全性变得至关重要。Kubernetes 提供了多种安全机制来保护集群及其资源免受未授权访问和潜在威胁的影响。其中&#xff0c;基于角色的访问控制&#xff08;Role-Based Access Control, 简称 RBAC&#xff09;是…...

编程日记 2025/5/14 13:39:50

排序算法--快速排序

快速排序是高效的排序算法&#xff0c;平均时间复杂度为 O(nlog⁡n)&#xff0c;适合大规模数据排序。 1.挖坑法 2左右指针法 3.前后指针法 // 交换两个元素的值 void swap(int* a, int* b) {int temp *a;*a *b;*b temp; }// 分区函数&#xff0c;返回分区点的索引 int par…...

编程日记 2025/5/10 11:32:48

npm知识

npm 是什么 npm 为你和你的团队打开了连接整个 JavaScript 天才世界的一扇大门。它是世界上最大的软件注册表&#xff0c;每星期大约有 30 亿次的下载量&#xff0c;包含超过 600000 个包&#xff08;package&#xff09;&#xff08;即&#xff0c;代码模块&#xff09;。来自…...

编程日记 2025/5/13 8:41:31

雷电等基于VirtualBox的Android模拟器映射串口和测试CSerialPort串口功能

雷电等基于VirtualBox的Android模拟器映射串口和测试CSerialPort串口功能 1. 修改VirtualBox配置文件映射串口 模拟器配置文件vms/leidian0/leidian.vbox。 在UART标签下增加(修改完成后需要将leidian.vbox修改为只读) <Port slot"1" enabled"true"…...

编程日记 2025/5/14 13:38:37

http请求中的headers和body内容设置

1.headers 1.1 内容相关 headers {Content-Type: application/json, # 或 application/x-www-form-urlencoded, multipart/form-dataContent-Length: 1234, # 内容长度Accept: application/json, # 期望的返回格式Accept-Encoding: gzip, deflate, # 支持的压缩方式Acce…...

编程日记 2025/5/6 4:15:12

Python语言的安全开发

Python语言的安全开发 引言 在信息技术迅速发展的今天&#xff0c;网络安全问题愈发凸显。随着Python语言的广泛应用&#xff0c;尤其是在数据分析、人工智能、Web开发等领域&#xff0c;其安全问题越来越受到重视。Python作为一门高效且易于学习的编程语言&#xff0c;虽然在…...

编程日记 2025/5/14 13:52:20

[LeetCode]day13 19.删除链表的倒数第n个结点

19. 删除链表的倒数第 N 个结点 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5]示例 2&a…...

编程日记 2025/5/10 8:48:12

进程的环境变量

export MUDUO_LOG_DEBUG1 ./testif (::getenv("MUDUO_LOG_TRACE"))return true;有时在程序运行前&#xff0c;我们希望设置环境变量。此处::表示全局命名空间。 在类 Unix 系统&#xff08;如 Linux、macOS&#xff09;中&#xff0c;环境变量并不直接存储在堆、栈或…...

编程日记 2025/5/10 16:14:40

《深度揭秘LDA：开启人工智能降维与分类优化的大门》

在当今人工智能蓬勃发展的时代&#xff0c;数据成为了驱动技术进步的核心要素。随着数据采集和存储技术的飞速发展&#xff0c;我们所面临的数据量不仅日益庞大&#xff0c;其维度也愈发复杂。高维数据虽然蕴含着丰富的信息&#xff0c;但却给机器学习算法带来了一系列严峻的挑…...

编程日记 2025/5/11 6:49:55

UE编辑器工具

如何自己制作UE小工具提高工作效率 在虚幻编辑器用户界面中&#xff0c;可以使用各种各样的可视化工具来设置项目&#xff0c;设计和构建关卡&#xff0c;创建游戏性交互等等。但有些时候&#xff0c;当你确定了需要编辑器执行的操作后&#xff0c;可能想要通过编程方式调用它…...

编程日记 2025/5/12 23:07:22

.找到字符串中所有字母异位词（滑动窗口）

给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 示例 1: 输入: s "cbaebabacd", p "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "…...

编程日记 2025/5/14 13:35:01

力扣 121. 买卖股票的最佳时机

&#x1f517; https://leetcode.cn/problems/best-time-to-buy-and-sell-stock 题目 nums 表示连续几天的股票价格&#xff0c;返回最大利润 思路 贪心&#xff0c;模拟 代码 class Solution { public:int maxProfit(vector<int>& prices) {int ans 0;int mi…...

编程日记 2025/5/9 2:33:23

c++ 冒泡排序

c 冒泡排序 冒泡排序是一种简单的排序算法&#xff0c;它通过重复遍历待排序的数列&#xff0c;比较每对相邻元素的大小&#xff0c;并在必要时交换它们的位置。这个过程会一直进行&#xff0c;直到没有需要交换的元素为止&#xff0c;这意味着数列已经排序完成。以下是用C实现…...

编程日记 2025/5/14 13:43:15

JMeter的详细学习路线

以下是一个适合新手的 **JMeter 详细学习路线**&#xff0c;从基础到实战逐步深入&#xff0c;帮助你系统掌握 JMeter 的核心功能和使用技巧。 --- ### **一、入门阶段&#xff1a;理解基础概念** 1. **了解性能测试基础** - 什么是性能测试&#xff1f; - 负载测…...

编程日记 2025/5/12 10:34:51

【C# 】图像资源的使用

在C#中&#xff0c;图像资源的使用方式方法主要依赖于你所使用的框架和库。以下是几种常见的使用图像资源的方法&#xff1a; Windows Forms 直接加载图像&#xff1a; 使用System.Drawing.Image.FromFile()方法可以直接从文件系统加载图像。 Image image Image.FromFile(&qu…...

编程日记 2025/5/14 13:15:20

3.PPT：华老师-计算机基础课程【3】

目录 NO12​ NO34​ NO56​ NO789​ NO12 根据考生文件夹下的Word文档“PPT素材.docx”中提供的内容在PPT.pptx中生成初始的6张幻灯片 新建幻灯片6张→ctrlc复制→ctrlv粘贴开始→新建幻灯片→幻灯片(从大纲)→Word文档注❗前提是&#xff1a;Word文档必须应用标题1、标题2…...

编程日记 2025/5/14 13:39:50

关于算尽圆周率

总有人提到圆周率算尽的问题&#xff0c;其实代码都已经在前面给出了&#xff0c;自己跑一下就明白了。 用语言描述的话&#xff0c;那就是&#xff1a; 前面几篇文章已经写清楚了&#xff0c;圆周率的本质就是无限分辨率前提下的可二分度量单位。 就像是自然对数底&#xf…...

编程日记 2025/5/12 13:06:24

动态获取脚本名称作为日志文件的名称

优点 独立性&#xff1a; 每个脚本的日志独立存储&#xff0c;避免日志混杂&#xff0c;便于排查问题。 灵活性&#xff1a; 支持动态获取脚本名称&#xff0c;无需手动指定日志记录器名称。 可扩展性&#xff1a; 可以轻松扩展日志格式、级别、存储路径等功能。 易用性&…...

编程日记 2025/5/13 1:13:22

JavaScript前后端交互-AJAX/fetch

摘自千峰教育kerwin的js教程 AJAX 1、AJAX 的优势 不需要插件的支持&#xff0c;原生 js 就可以使用用户体验好&#xff08;不需要刷新页面就可以更新数据&#xff09;减轻服务端和带宽的负担缺点&#xff1a; 搜索引擎的支持度不够&#xff0c;因为数据都不在页面上&#xf…...

编程日记 2025/5/11 14:04:57

2025 网络安全学习路线 非常详细 推荐学习

关键词&#xff1a;网络安全入门、渗透测试学习、零基础学安全、网络安全学习路线 首先咱们聊聊&#xff0c;学习网络安全方向通常会有哪些问题 1、打基础时间太长 学基础花费很长时间&#xff0c;光语言都有几门&#xff0c;有些人会倒在学习 linux 系统及命令的路上&#…...

编程日记 2025/5/12 16:08:46

尝试把clang-tidy集成到AWTK项目

前言 项目经过一段时间的耕耘终于进入了团队开发阶段&#xff0c;期间出现了很多问题&#xff0c;其中一个就是开会讨论团队的代码风格规范&#xff0c;目前项目代码风格比较混乱&#xff0c;有的模块是驼峰&#xff0c;有的模块是匈牙利&#xff0c;后面经过讨论&#xff0c;…...

编程日记 2025/5/12 20:54:30

04树 + 堆 + 优先队列 + 图（D1_树（D17_综合刷题练习））

目录 1. 二叉树的前序遍历&#xff08;简单&#xff09; 1.1. 题目描述 1.2. 解题思路 方法一&#xff1a;递归&#xff08;推荐使用&#xff09; 方法二&#xff1a;非递归&#xff08;扩展思路&#xff09; 2. 二叉树的中序遍历&#xff08;中等&#xff09; 2.1. 题目…...

编程日记 2025/5/10 17:25:24

C++ Primer 数组

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

编程日记 2025/5/13 2:16:23

Linux(Centos)安装allnnlp失败,jsonnet报错

Linux安装allnnlp失败,jsonnet报错 问题分析并解决1. 什么是 Software Collection (SCL)&#xff1f;2. 安装步骤2.1 安装 SCL 仓库支持2.2 安装 Devtoolset-7 提供的 C 编译器2.3 启用 Devtoolset-7 环境2.4 验证安装 3. 永久启用 Devtoolset-7 环境 问题 执行pip install al…...

编程日记 2025/5/14 9:29:27

小程序设计和开发：要如何明确目标和探索用户需求？

一、明确小程序的目标 确定业务目标 首先&#xff0c;需要明确小程序所服务的业务领域和目标。例如&#xff0c;是一个电商小程序&#xff0c;旨在促进商品销售&#xff1b;还是一个服务预约小程序&#xff0c;方便用户预订各类服务。明确业务目标有助于确定小程序的核心功能和…...

编程日记 2025/5/12 9:39:10

C#面试常考随笔12：游戏开发中常用的设计模式【C#面试题（中级篇）补充】

C#面试题&#xff08;中级篇&#xff09;&#xff0c;详细讲解&#xff0c;帮助你深刻理解&#xff0c;拒绝背话术&#xff01;-CSDN博客 简单工厂模式 优点&#xff1a; 根据条件有工厂类直接创建具体的产品 客户端无需知道具体的对象名字&#xff0c;可以通过配置文件创建…...

编程日记 2025/5/12 13:53:37

napalm ‘NXOSDriver‘ object has no attribute ‘port‘ 解决方案（随手记）

解决方案&#xff08;仍然使用ssh作为访问方式&#xff09; 使用napalm时&#xff0c;对于Cisco Nexus设备&#xff0c;默认采用的是443的api去访问获取数据&#xff0c;如果需要使用ssh的方式获取&#xff0c;需要特别指定get_network_driver(nxos_ssh) 使用443 https api的…...

编程日记 2025/5/13 8:41:17