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

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++中,我们可以使用多种算法来解决背包问题,下面我将详细介绍每个算法的实现和优缺点。

  1. 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)的时间和空间。

  1. 完全背包问题: 完全背包问题是背包问题中的一个变种,其中每个物品可以无限次地放入背包。我们同样可以使用动态规划来解决完全背包问题。具体算法如下:
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)的空间。

  1. 多重背包问题: 多重背包问题是背包问题中的另一种变种,其中每个物品有一个数量限制。我们可以使用动态规划来解决多重背包问题,类似于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)的时间和空间。

  1. 分数背包问题: 分数背包问题是背包问题中的一种特殊情况,其中每个物品可以被分割成任意大小的部分。我们可以使用贪心算法来解决分数背包问题,基于物品的单位价值进行排序,然后依次选择单位价值最高的物品放入背包中,直到背包没有空间为止。具体算法如下:
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&#xff0c;大家好啊&#xff0c;我是文宇&#xff0c;不是文字&#xff0c;是文宇哦。 斐波那契数列&#xff08;Fibonacci Sequence&#xff09; 斐波那契数列&#xff08;Fibonacci Sequence&#xff09;是一个经典的数学问题&#xff0c;其中每个数都是前两个…...

connect的非阻塞模式

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

jenkins面试题全集

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

Python中最好学和最实用的有哪些库和框架

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

文件解析的终极工具:Apache Tika

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

Hadoop 重要监控指标

某安卓逆向课程打包下载&#xff08;92节课&#xff09; ​​https://pan.quark.cn/s/53cec8b8055a ​​ 某PC逆向课程&#xff08;100节课打包下载&#xff09; ​​https://pan.quark.cn/s/e38f2b24f36c​​ Hadoop 是一个开源的分布式存储和计算框架&#xff0c;广泛应用…...

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&#xff0c; 给父进程返回子进程的 pid &#xff1f;b. 一个函数是如何做到两次的&#xff1f;c. fork 函数在干什么&#xff1f;d. 一个变量怎么做到拥有不同的内容的&#xff1f;e. 拓展&#xff1a;…...

huawei 路由 RIP 协议中三种定时器的工作原理

RFC2453 定义的三种 RIP 协议定时器 更新定时器&#xff08;Update Timer&#xff09;&#xff1a;用于触发更新报文的发送&#xff0c;超时时间为 30 秒。老化定时器&#xff08;Age Timer&#xff09;&#xff1a;如果在老化时间内没有收到邻居发送的响应报文&#xff0c;则…...

HTML常见标签——超链接a标签

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

Python 爬虫入门(一):从零开始学爬虫 「详细介绍」

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

Linux嵌入式学习——数据结构——概念和Seqlist

数据结构 相互之间存在一种或多种特定关系的数据元素的集合。 逻辑结构 集合&#xff0c;所有数据在同一个集合中&#xff0c;关系平等。 线性&#xff0c;数据和数据之间是一对一的关系。数组就是线性表的一种。 树&#xff0c; 一对多 图&#xff0c;多对多 …...

iOS ------ Block的相关问题

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

conda issue

Conda 是一个跨平台、通用的二进制包管理器。它是 Anaconda 安装使用的包管理器&#xff0c;但它也可能用于其他系统。Conda 完全用 Python 编写&#xff0c;并且是 BSD 许可的开源。通用意味着大部分的包都可以用它进行管理&#xff0c;很像一个跨平台版本的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交易实战] 第十八篇 期货查询类函数和期货设置类函数

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

STM32智能家居控制系统教程

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

FPGA 中的 IOE与IO BANK

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

ADetailer模型+Stable Diffusion的inpainting功能是如何对遮罩区域进行修复生成的ADetailer

模型选则&#xff1a; face_yolov8n.pt 和 face_yolov8s.pt&#xff1a; 用途&#xff1a;用于人脸检测。特点&#xff1a;YOLOv8n 是轻量级版本&#xff0c;适合资源有限的设备&#xff1b;YOLOv8s 是标准版本&#xff0c;检测精度更高。 hand_yolov8n.pt&#xff1a; 用途&am…...

【博士每天一篇文献-综述】2024机器遗忘最新综述之一:An overview of machine unlearning

1 介绍 年份&#xff1a;2024 作者&#xff1a; 期刊&#xff1a; High-Confidence Computing&#xff08;2区&#xff09; 引用量&#xff1a;0 Li C, Jiang H, Chen J, et al. An overview of machine unlearning[J]. High-Confidence Computing, 2024: 100254 本文详细提供…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...