当前位置: 首页 > 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 本文详细提供…...

智慧医疗能源事业线深度画像分析(上)

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

Appium+python自动化(十六)- ADB命令

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

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

苍穹外卖--缓存菜品

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

Spring数据访问模块设计

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

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...