c++中的斐波那契数列(Fibonacci Sequence)和背包问题(Knapsack Problem)
前言
hello,大家好啊,我是文宇,不是文字,是文宇哦。
斐波那契数列(Fibonacci Sequence)
斐波那契数列(Fibonacci Sequence)是一个经典的数学问题,其中每个数都是前两个数的和。在C++中,我们可以使用多种算法来计算斐波那契数列,下面我将详细介绍每个算法的实现和优缺点。
递归算法
递归算法是最直观和简单的方法来实现斐波那契数列。通过递归调用函数来计算每一个数。具体实现如下:
int fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n - 1) + fibonacci(n - 2);
}
递归算法的优点是简洁易懂,容易理解。但是它的缺点是重复计算量大,在计算较大的斐波那契数时,可能会导致性能问题。
迭代算法
为了避免递归算法的重复计算,我们可以使用迭代算法来计算斐波那契数列。迭代算法的基本思路是从前往后依次计算每一个数,保存中间结果。具体实现如下:
int fibonacci(int n) {if (n <= 1) {return n;}int a = 0;int b = 1;int c;for (int i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return c;
}
迭代算法的优点是避免了递归算法的重复计算,性能相对较好。但是它的缺点是需要编写较多的代码,可读性稍差。
数组算法
我们还可以使用数组来保存斐波那契数列的中间结果,以进一步提高性能。具体实现如下:
int fibonacci(int n) {if (n <= 1) {return n;}int* fib = new int[n + 1];fib[0] = 0;fib[1] = 1;for (int i = 2; i <= n; i++) {fib[i] = fib[i - 1] + fib[i - 2];}int result = fib[n];delete[] fib;return result;
}
数组算法的优点是性能较好,同时代码相对简单。但是它的缺点是需要额外的内存空间来保存数组,可能导致内存泄漏。
公式算法
在斐波那契数列的研究中,我们还发现了一个通项公式来直接计算第n个斐波那契数。具体公式如下:
int fibonacci(int n) {double goldenRatio = (1 + sqrt(5)) / 2;return round(pow(goldenRatio, n) / sqrt(5));
}
公式算法的优点是计算简单快速,但是它的缺点是可能会有精度问题,同时不太容易理解。
综上所述,以上四种算法都可以用来实现斐波那契数列。具体选择哪种算法取决于实际需求和性能要求。如果不考虑性能,递归算法是最简单直观的方法;如果性能较重要,迭代算法和数组算法可以提供较好的性能;如果要求精确计算,公式算法是一个很好的选择。
背包问题(Knapsack Problem)
背包问题(Knapsack Problem)是一个经典的组合优化问题,在计算机科学领域中被广泛研究和应用。它的基本问题可以描述为,给定一个背包的容量和一系列物品的重量和价值,如何选择物品放入背包中,使得背包中物品的总价值最大。
在C++中,我们可以使用多种算法来解决背包问题,下面我将详细介绍每个算法的实现和优缺点。
- 0/1背包问题: 0/1背包问题是背包问题中最基本的形式,其中每个物品要么完全放入背包,要么完全不放入。我们可以使用动态规划来解决0/1背包问题。具体算法如下:
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {int n = weights.size();vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));for (int i = 1; i <= n; i++) {for (int j = 1; j <= capacity; j++) {if (weights[i - 1] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);}}}return dp[n][capacity];
}
0/1背包问题的关键是构建一个二维的动态规划数组,利用前一个状态的结果来更新当前状态。它的优点是能够得到精确的解,但是它的缺点是时间复杂度较高,需要O(n * capacity)的时间和空间。
- 完全背包问题: 完全背包问题是背包问题中的一个变种,其中每个物品可以无限次地放入背包。我们同样可以使用动态规划来解决完全背包问题。具体算法如下:
int knapsackComplete(vector<int>& weights, vector<int>& values, int capacity) {int n = weights.size();vector<int> dp(capacity + 1, 0);for (int i = 0; i < n; i++) {for (int j = weights[i]; j <= capacity; j++) {dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);}}return dp[capacity];
}
完全背包问题与0/1背包问题的区别在于内层循环的顺序,我们需要从小到大遍历容量,而不是从大到小。它的优点是时间复杂度相对较低,只需要O(n * capacity)的时间和O(capacity)的空间。
- 多重背包问题: 多重背包问题是背包问题中的另一种变种,其中每个物品有一个数量限制。我们可以使用动态规划来解决多重背包问题,类似于0/1背包问题。具体算法如下:
int knapsackMultiple(vector<int>& weights, vector<int>& values, vector<int>& quantities, int capacity) {int n = weights.size();vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));for (int i = 1; i <= n; i++) {for (int j = 1; j <= capacity; j++) {for (int k = 0; k <= quantities[i - 1] && k * weights[i - 1] <= j; k++) {dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weights[i - 1]] + k * values[i - 1]);}}}return dp[n][capacity];
}
多重背包问题与0/1背包问题的区别在于内层循环的次数,我们需要遍历每个物品的数量限制。它的优点是能够解决具有数量限制的背包问题,但是它的缺点是时间复杂度较高,需要O(n * quantity * capacity)的时间和空间。
- 分数背包问题: 分数背包问题是背包问题中的一种特殊情况,其中每个物品可以被分割成任意大小的部分。我们可以使用贪心算法来解决分数背包问题,基于物品的单位价值进行排序,然后依次选择单位价值最高的物品放入背包中,直到背包没有空间为止。具体算法如下:
double knapsackFractional(vector<int>& weights, vector<int>& values, int capacity) {int n = weights.size();vector<pair<double, int>> ratios(n);for (int i = 0; i < n; i++) {ratios[i] = {static_cast<double>(values[i]) / weights[i], i};}sort(ratios.rbegin(), ratios.rend()); // 按照单位价值降序排序double result = 0.0;for (int i = 0; i < n; i++) {int index = ratios[i].second;if (weights[index] <= capacity) {result += values[index];capacity -= weights[index];} else {result += capacity * ratios[i].first;break;}}return result;
}
分数背包问题的优点是时间复杂度较低,只需要O(n * log(n))的时间和O(n)的空间,但是它的缺点是不能得到精确的解。
综上所述,以上四种算法都可以用来解决不同形式的背包问题。具体选择哪种算法取决于实际需求和性能要求。如果物品数量较少且要求精确解,可以使用0/1背包算法;如果物品数量较多或者需要更高的性能,可以使用完全背包算法;如果需要考虑物品的数量限制,可以使用多重背包算法;如果物品可以被分割成任意大小,可以使用分数背包算法。
结语
今天的算法是动态规划,脑子有点不好使了。
相关文章:

c++中的斐波那契数列(Fibonacci Sequence)和背包问题(Knapsack Problem)
前言 hello,大家好啊,我是文宇,不是文字,是文宇哦。 斐波那契数列(Fibonacci Sequence) 斐波那契数列(Fibonacci Sequence)是一个经典的数学问题,其中每个数都是前两个…...

connect的非阻塞模式
本文参考:connect 函数在阻塞和非阻塞模式下的行为 一般情况下,在使用connect连接服务端时,需要等待一会儿才会函数才会返回,导致程序阻塞。为了降低阻塞的影响,我们可能会单独开个线程处理connect请求,例…...

jenkins面试题全集
1. 简述什么是Jenkins ? Jenkins是一个开源的持续集成的服务器,Jenkins开源帮助我们自动构建各类项目。 Jenkins强大的插件式,使得Jenkins可以集成很多软件,可以帮助我们持续集成我们的工程项目,对于我们测试来说&…...

Python中最好学和最实用的有哪些库和框架
Python拥有丰富的库和框架,这些库和框架覆盖了从数据处理、科学计算、Web开发到机器学习等多个领域。以下是一些值得学习的Python库和框架: 数据处理与科学计算 NumPy 描述:NumPy是Python中用于科学计算的一个库,它提供了一个强…...

文件解析的终极工具:Apache Tika
文件解析的终极工具:Apache Tika Apache Tika 简介 Apache Tika 是一个开源的、跨平台的库,用于检测、提取和解析各种类型文件的元数据。 它支持多种文件格式,包括文档、图片、音频和视频。 Tika是一个底层库,经常用于搜索引擎…...

Hadoop 重要监控指标
某安卓逆向课程打包下载(92节课) https://pan.quark.cn/s/53cec8b8055a 某PC逆向课程(100节课打包下载) https://pan.quark.cn/s/e38f2b24f36c Hadoop 是一个开源的分布式存储和计算框架,广泛应用…...

oracle 查询锁表
oracle 查询锁表 SELECT o.object_name, s.sid, s.serial#, p.spid, s.username, s.program FROM v l o c k e d o b j e c t l J O I N d b a o b j e c t s o O N l . o b j e c t i d o . o b j e c t i d J O I N v locked_object l JOIN dba_objects o ON l.object_id …...

进程概念(三)----- fork 初识
目录 前言1. pid && ppid2. forka. 为什么 fork 要给子进程返回 0, 给父进程返回子进程的 pid ?b. 一个函数是如何做到两次的?c. fork 函数在干什么?d. 一个变量怎么做到拥有不同的内容的?e. 拓展:…...

huawei 路由 RIP 协议中三种定时器的工作原理
RFC2453 定义的三种 RIP 协议定时器 更新定时器(Update Timer):用于触发更新报文的发送,超时时间为 30 秒。老化定时器(Age Timer):如果在老化时间内没有收到邻居发送的响应报文,则…...

HTML常见标签——超链接a标签
一、a标签简介 二、a标签属性 href属性 target属性 三、a标签的作用 利用a标签进行页面跳转 利用a标签返回页面顶部以及跳转页面指定区域 利用a标签实现文件下载 一、a标签简介 <a>标签用于做跳转、导航,是双标签,记作<a></a>&#…...

Python 爬虫入门(一):从零开始学爬虫 「详细介绍」
Python 爬虫入门(一):从零开始学爬虫 「详细介绍」 前言1.爬虫概念1.1 什么是爬虫?1.2 爬虫的工作原理 2. HTTP 简述2.1 什么是 HTTP?2.2 HTTP 请求2.3 HTTP 响应2.4 常见的 HTTP 方法 3. 网页的组成3.1 HTML3.2 CSS3.…...

Linux嵌入式学习——数据结构——概念和Seqlist
数据结构 相互之间存在一种或多种特定关系的数据元素的集合。 逻辑结构 集合,所有数据在同一个集合中,关系平等。 线性,数据和数据之间是一对一的关系。数组就是线性表的一种。 树, 一对多 图,多对多 …...

iOS ------ Block的相关问题
Block的定义 Block可以截获局部变量的匿名函数, 是将函数及其执行上下文封装起来的对象。 Block的实现 通过Clang将以下的OC代码转化为C代码 // Clang xcrun -sdk iphoneos clang -arch arm64 -rewrite-objc main.m//main.m #import <Foundation/Foundation.…...

conda issue
Conda 是一个跨平台、通用的二进制包管理器。它是 Anaconda 安装使用的包管理器,但它也可能用于其他系统。Conda 完全用 Python 编写,并且是 BSD 许可的开源。通用意味着大部分的包都可以用它进行管理,很像一个跨平台版本的apt或者yum&#x…...

为了解决地图引入鉴权失败的解决方案
在以下文件中需要添加相应代码 app/controller/CollageProduct.php app/view/designer_page/designer_editor.html app/view/designer_page/designer.html app/controller/Freight.php app\controller\Business.php app\controller\DesignerPage.php 只有这样才能保证htt…...

[ptrade交易实战] 第十八篇 期货查询类函数和期货设置类函数
前言 今天主要和大家分享的是期货查询类的函数和期货设置类的函数! 具体的开通渠道可以看文章末尾! 一、get_margin_rate—— 获取用户设置的保证金比例 保证金是期货交易中的一个重点,这个函数就是用来获取我们设置的保证金比例的&#…...

STM32智能家居控制系统教程
目录 引言环境准备智能家居控制系统基础代码实现:实现智能家居控制系统 4.1 数据采集模块 4.2 数据处理与分析模块 4.3 通信与网络系统实现 4.4 用户界面与数据可视化应用场景:家居监测与优化问题解决方案与优化收尾与总结 1. 引言 智能家居控制系统通…...

FPGA 中的 IOE与IO BANK
IO bank(输入/输出bank) 定义:IO bank 是 FPGA 中一组 IOE 的集合,通常共享相同的电源电压、时钟域和时序管理。每个 IO bank 包含多个 IOE,它们可以根据需要分配给不同的信号处理任务。作用:IO bank 的存…...

ADetailer模型+Stable Diffusion的inpainting功能是如何对遮罩区域进行修复生成的ADetailer
模型选则: face_yolov8n.pt 和 face_yolov8s.pt: 用途:用于人脸检测。特点:YOLOv8n 是轻量级版本,适合资源有限的设备;YOLOv8s 是标准版本,检测精度更高。 hand_yolov8n.pt: 用途&am…...

【博士每天一篇文献-综述】2024机器遗忘最新综述之一:An overview of machine unlearning
1 介绍 年份:2024 作者: 期刊: High-Confidence Computing(2区) 引用量:0 Li C, Jiang H, Chen J, et al. An overview of machine unlearning[J]. High-Confidence Computing, 2024: 100254 本文详细提供…...

【机器学习】Jupyter Notebook如何使用之基本步骤和进阶操作
引言 Jupyter Notebook 是一个交互式计算环境,它允许创建包含代码、文本和可视化内容的文档 文章目录 引言一、基本步骤1.1 启动 Jupyter Notebook1.2 使用 Jupyter Notebook 仪表板1.3 在笔记本中工作1.4 常用快捷键1.5 导出和分享笔记本 二、进阶用法2.1 组织笔…...

C++ | Leetcode C++题解之第279题完全平方数
题目: 题解: class Solution { public:// 判断是否为完全平方数bool isPerfectSquare(int x) {int y sqrt(x);return y * y x;}// 判断是否能表示为 4^k*(8m7)bool checkAnswer4(int x) {while (x % 4 0) {x / 4;}return x % 8 7;}int numSquares(i…...

Vue 3 响应式高阶用法之 `shallowRef()` 详解
Vue 3 响应式高阶用法之 shallowRef() 详解 文章目录 Vue 3 响应式高阶用法之 shallowRef() 详解简介一、使用场景1.1 深层嵌套对象的性能优化1.2 需要部分响应式的场景 二、基本使用2.1 引入 shallowRef2.2 定义 shallowRef 三、功能详解3.1 浅层响应式3.2 与 ref 的对比 四、…...

流量录制与回放:jvm-sandbox-repeater工具详解
在软件开发和测试过程中,流量录制与回放是一个非常重要的环节,它可以帮助开发者验证系统在特定条件下的行为是否符合预期。本文将详细介绍一款强大的流量录制回放工具——jvm-sandbox-repeater,以及如何利用它来提高软件测试的效率和质量。 …...

内网渗透—内网穿透工具NgrokFRPNPSSPP
前言 主要介绍一下常见的隧道搭建工具,以此来达到一个内网穿透的目的。简单说一下实验滴环境吧,kali作为攻击机,winserver2016作为目标靶机。 kali 192.168.145.171 winserver2016 10.236.44.127 显然它们处于两个不同的局域网,…...

嵌入式中传感器数据处理方法
大家好,在传感器使用中,我们常常需要对传感器数据进行各种整理,让应用获得更好的效果,以下介绍几种常用的简单处理方法: 加权平滑:平滑和均衡传感器数据,减小偶然数据突变的影响。 抽取突变:去除静态和缓慢变化的数据背景,强调瞬间变化。 简单移动平均线:保留数据流最…...

生成式 AI 的发展方向,是 Chat 还是 Agent?
据《福布斯》报道,商业的未来是自动化。他们报告说,自动化的应用是不可避免的,“工人们即将被一个圈子和一套规则包围,要严格遵守,不能偏离。得益于聊天机器人ChatGPT于2022年11月推出所带来的强劲加持,202…...

金字塔监督在人脸反欺骗中的应用
介绍 论文地址:https://arxiv.org/pdf/2011.12032.pdf 近年来,人脸识别技术越来越普及。在智能手机解锁和进出机场时,理所当然地会用到它。人脸识别也有望被用于管理今年奥运会的相关人员。但与此同时,人们对人脸欺骗的关注度也…...

vue3——两种利用自定义指令实现防止按钮重复点击的方法
方法一:利用定时器设置时间,下方代码设置时间为1秒 但是有个缺点:请求如果很慢,1秒钟还没有好,那么该方法就没用了 // 利用定时器:1秒之后才能再次点击app.directive(preventReClick, {mounted: (el, bind…...

Chrome谷歌浏览器Console(控制台)显示文件名及行数
有没有这样的困扰?Chrome谷歌浏览器console(控制台)不显示编译文件名及行数? 设置(Settings)- > 忽略列表(lgnore List)-> 自定义排除规则(Custom exclusion rules) 将自定义排除规则…...