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 本文详细提供…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...