C++的算法:贪心算法

server/2025/1/16 0:54:11/

        贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效,它所做的每一个选择都是基于一个局部最优决策,从而希望导致全局最优解。然而,贪心算法并不总是能得到全局最优解,因此需要确保所解决问题确实具备贪心选择的性质。

        选择贪心算法解决问题时,需要满足两个条件:

        1. 贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法能够正确的必要条件。
        2. 最优子结构性质:一个问题的最优解包含其子问题的最优解。也就是说,我们可以通过将问题的最优解分解成若干个子问题的最优解来构造整个问题的最优解。

        贪心算法的应用示例一:求解背包问题。

        背包问题是一个典型的贪心算法应用问题。假设我们有一组物品,每个物品都有自己的重量和价值,现在给定一个背包的容量,我们希望在不超过背包容量的前提下,使得背包内物品的总价值最大。代码如下。

#include <iostream>
#include <vector>
#include <algorithm>// 定义物品结构体
struct Item {int weight;int value;double ratio; // 价值与重量的比值// 根据比值初始化结构体Item(int w, int v) : weight(w), value(v), ratio(static_cast<double>(v) / w) {}
};// 根据比值降序排序
boo

http://www.ppmy.cn/server/47674.html

相关文章

LeetCode-103. 二叉树的锯齿形层序遍历【树 广度优先搜索 二叉树】

LeetCode-103. 二叉树的锯齿形层序遍历【树 广度优先搜索 二叉树】 题目描述&#xff1a;解题思路一&#xff1a;层序遍历&#xff0c;唯一区别就是ans.append(level[::-1] if len(ans) % 2 else level)背诵版&#xff1a;解题思路三&#xff1a;0 题目描述&#xff1a; 给你二…

Python 高手编程系列三:用于保持跨版本兼容性的常用工具和技术

在 Python 不同版本之间保持兼容性是一项挑战。根据项目的大小不同&#xff0c;这项挑战可能 会增加许多额外的工作量&#xff0c;但绝对可行&#xff0c;也很值得去做。对于在许多环境中都会用到的 Python 包来说&#xff0c;必须要保持跨版本兼容性。如果开源包没有定义明确并…

Android AAudio——C API控制音频流(四)

上一篇文章我们介绍了 C API 中音频流的创建流程,以及打开音频流操作,这里我们再来看一下音频流的其他操作流程 一、音频流操作介绍 1、操作流程图 下图是状态变化流程图,虚线框表示瞬时状态,实线框表示稳定状态。 2、操作函数 上图中主要包含下面几个操作函数: aaudio…

微信小程序动画和Canvas笔记

微信小程序动画和Canvas 动画 使用wx.createAnimation创建动画对象 // 创建动画对象 const animation wx.createAnimation({duration: 1000, // 动画持续时间timingFunction: ease, // 动画速度曲线delay: 0, // 动画延迟时间transformOrigin: 50% 50% 0, // 动画的中心点 …

java项目使用jsch下载ftp文件

pom <dependency><groupId>com.jcraft</groupId><artifactId>jsch</artifactId><version>0.1.55</version> </dependency>demo1&#xff1a;main方法直接下载 package com.example.controller;import com.jcraft.jsch.*; im…

进程间通信(27000字超详解)

&#x1f30e;进程间通信 文章目录&#xff1a; 进程间通信 进程间通信简介       进程间通信目的       初识进程间通信       进程间通信的分类 匿名管道通信       认识管道       匿名管道       匿名管道测试       管道的四种…

OpenCV学习(4.1) 改变颜色空间

1.目标 在本教程中&#xff0c;你将学习如何将图像从一个色彩空间转换到另一个&#xff0c;像BGR↔灰色&#xff0c;BGR↔HSV等除此之外&#xff0c;我们还将创建一个应用程序&#xff0c;以提取视频中的彩色对象你将学习以下功能&#xff1a;cv2.cvtColor&#xff0c;**cv2.i…

LeetCode刷题 | Day 2 最长严格递增或递减子列表(Longest Increasing or Decreasing SubList)

LeetCode刷题 | Day 2 最长严格递增或递减子列表(Longest Increasing Decreasing SubList) 文章目录 LeetCode刷题 | Day 2 最长严格递增或递减子列表(Longest Increasing Decreasing SubList)前言一、题目概述二、解题方法2.1 动态规划思想2.1.1 思路讲解2.1.2 伪代码 + 逐…