算法设计与分析(贪心法)

学习的最大理由是想摆脱平庸,早一天就多一份人生的精彩;迟一天就多一天平庸的困扰。各位小伙伴,如果您:
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持,想组团高效学习…
想写博客但无从下手,急需写作干货注入能量…
热爱写作,愿意让自己成为更好的人…

文章目录

  • 一、贪心法的基本思想
  • 二、贪心法的基本要素
    • 1.最优子结构性质
    • 2.贪心选择性质
  • 三、贪心法的解题步骤及算法设计模式
    • 1、步骤:
    • 2、设计模式
  • 四、会场安排问题
  • 五、最优装载问题
  • 总结


一、贪心法的基本思想

贪心法是一种稳扎稳打的算法,他从问题的摸一个初始解出发,在每一个阶段都根据贪心策略来做出当前最优决策,逐步逼近给定目标,尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时,算法终止。也可以理解为:以逐步的局部最优,达到最终的全局最优

二、贪心法的基本要素

1.最优子结构性质

当一个问题的最优解一定包含其他子问题的最优解时,称此问题具有最优子结构性质。(一个问题能够分解成各个子问题来解决,通过各个子问题的最优解能递推到原问题的最优解,此时原问题的最优解一定包含各个子问题的最优解,这是能够采用贪心法来求解问题的关键)

在分析问题是否具有最优子结构性质时,通常先设出问题的最优解,给出子问题的解一定是最优的结论。然后,采用反证法证明“子问题的解一定时最优的”结论成立。证明思路是:设原问题的最优解导出子问题的解不是最优的,然后在这个假设下可以构造出比原问题的最优解更好的解,从而导致矛盾。

2.贪心选择性质

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择获得,即通过一系列的逐步局部最优选择使得最终的选择方案是全局最优的。其中每次所做的选择,可以依赖于以前的选择,但不依赖于将来所做的选择。

贪心选择性质所做的是一个非线性的子问题处理流程,即一个子问题并不依赖于另一个子问题,但是子问题间有严格的顺序性。

三、贪心法的解题步骤及算法设计模式

1、步骤:

  • 1.分解:
    将原问题分解为若干个相互独立的阶段。

  • 2.解决:
    对于每个阶段依据贪心策略进行贪心选择,求出局部的最优解。

  • 3.合并:
    将各个阶段的解合并为原问题的一个可行解。

2、设计模式

Greedy(A,n)
{
    //A[0:n-1]包含n个输入,即A是问题的输入集合
    将解集合solution初始化为空;
    for(i=0;i<n;i++)                        //原问题分解为n个阶段
    {
        x=select(A);                        //依据贪心策略做贪心选择,求得局部最优解
        if(x可以包含在solution)              //判断解集合solution在加入x后是否满足约束条件
            solution=union(solution,x);    //部分局部最优解进行合并
    }
    return (解向量solution);                //n个阶段完成后,得到原问题的最优解
}

四、会场安排问题

此问题的核心思想是:每次从剩下未安排的会议中选择具有最早结束时间且不会与已安排的会议重叠的会议来安排。这样可以使下一个会议尽快开始。

1)实现活动安排问题的贪心算法。

测试数据可选用:

i12345678910
Begin1325356882
End45678910111213
#include <iostream>
using namespace std;
void Select(int n, int A[],int B[], bool C[])
{
	int i, j;
	C[1] = true;
	j = 1, i = 2;
	while (i <= n)
	{
		if (A[i] > B[j]) {
			C[i] = true;
			j = i;
		}
		else {
			C[i] = false;
		}
		i++;
	}
};


int main()
{
	int A[11] = { 0,1,3,2,5,3,5,6,8,8,2 },
		B[11] = { 0,4,5,6,7,8,9,10,11,12,13 };
	bool C[11];
	Select(11, A, B, C);
	cout << "活动安排如下:" << endl;
	for (int k = 1; k <= 11; k++)
	{
		while (C[k])
		{
			cout << A[k]<<"  "<<B[k] << endl;
			break;
		}
	}
	return 0;
}

运算截图如下:
在这里插入图片描述

五、最优装载问题

2)实现最优装载的贪心算法。

测试数据可选用:

假设轮船限重12kg

i12345
Wi (kg)84257
#include "TanXin2.h"
#include<iostream>
using namespace std;
#define Max 10
typedef struct {
	int *elem;
	int length;
}SqList;

int InitList(SqList &L)//构造并初始化
{
	L.elem = new int[Max];
	if (!L.elem) return 0;
	L.length = 0;
	return 1;
}

void InputList(SqList &L,SqList &LB, int n)
{
	L.length = 0;
	if (n<0 || n>Max) return;
	cout << "请输入顺序表" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> L.elem[i];
		L.length++;
	}
	for (int j = 0; j < n; j++)
	{
		LB.elem[j] = L.elem[j];
		LB.length++;
	}
}

void OutputList(SqList L)
{
	for (int i = 0; i < L.length; i++)
	{
		cout << L.elem[i] << " ";

	}
}

void Compare(SqList &L)//冒泡排序
{
	int i, j, e;
	for (i = 1; i <= L.length; i++)
	{
		for (j = 0; j < L.length - i; j++)
		{
			if (L.elem[j] > L.elem[j + 1])
			{
				e = L.elem[j];
				L.elem[j] = L.elem[j + 1];
				L.elem[j + 1] = e;
			}
		}
	}
}

int LocateElem(SqList L, int e)//查找数据是否在顺序表内
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e) return i + 1;//查找成功,返回序号i+1
	}
	return 0;//查找失败,返回0
}

void Select(SqList &L,SqList &LB,int m)
{
	int sum = 0;
	for (int i = 0; i < L.length; i++)
	{
		if ((sum + L.elem[i]) < m)
		{
			sum += L.elem[i];
			cout<< LocateElem(LB, L.elem[i]) <<"  "<< L.elem[i] << endl;
		}
		else {
			break;
		}
	}
}

int main()
{
	int n = 5,m=12;
	SqList LA,LB;
	InitList(LA);
	InitList(LB);
	InputList(LA,LB,n);
	Compare(LA);
	cout << "所选择的为:" << endl;
	Select(LA,LB,m);

}

代码运行截图如下:

在这里插入图片描述


总结

以上就是算法设计与分析(贪心法)的相关知识点,希望对你有所帮助。
积跬步以至千里,积怠惰以至深渊。时代在这跟着你一起努力哦!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/466116.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Vulnhub - Symfonos

希望和各位大佬一起学习&#xff0c;如果文章内容有错请多多指正&#xff0c;谢谢&#xff01; 个人博客链接&#xff1a;CH4SER的个人BLOG – Welcome To Ch4sers Blog Symfonos 靶机下载地址&#xff1a;https://www.vulnhub.com/entry/symfonos-1,322/ 0x01 信息收集 …

[保姆级教程]Windows安装MongoDB教程

文章目录 MongoDB安装包下载1.点击进入mongodb官网2.点击MongoDB Community Edition&#xff08;社区版&#xff09;&#xff0c;进入下图界面3.选择版本4.下载5.安装6.勾选同意协议&#xff0c;点击“Next"7.选择自定义安装8.点击“Next"9.修改到合适的地址10.点击i…

影响汇率的因素?fpmarkets澳福总结几个

汇率对于刚刚开始外汇交易的新手来说非常重要&#xff0c;这不是没有道理的&#xff0c;了解汇率如何变化以及怎么变化有助于在外汇交易中获得稳定的利润。那么影响汇率的因素有哪些&#xff1f;fpmarkets澳福总结几个。 任何国家货币的汇率都是由市场决定的。主要的市场因素是…

盲盒抽卡机小程序开发:开启惊喜之旅,探索无限可能

随着互联网的快速发展&#xff0c;消费者的购物体验也在不断升级。盲盒文化&#xff0c;以其独特的魅力和惊喜感&#xff0c;正逐渐成为年轻人追求潮流、享受乐趣的新选择。为了满足广大盲盒爱好者的需求&#xff0c;我们精心打造了这款盲盒抽卡机小程序&#xff0c;为用户带来…

代码随想录算法训练营第43天 | 1049.最后一块石头的重量II ,494.目标和,474.一和零

动态规划章节理论基础&#xff1a; https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 1049.最后一块石头的重量II 题目链接&#xff1a;https://leetcode.cn/problems/last-stone-weight-ii/ 思路&#xff1a; …

阿里巴巴国际站商品采集商品信息抓取API免费测试入口(英文商品信息跨境电商商品信息自动化抓取)

alibaba.item_get 获取商品详情信息 alibaba.item_search 关键字搜索商品列表 进入API测试页&#xff0c;获取key和密钥 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥api_nameString是API接口名称…

Docker学习之使用harbor搭建私有仓库(超详解析)

实验目的&#xff1a; 使用centos7&#xff0c;基于harbor构建私有仓库 实验步骤&#xff1a; 下载相关安装包和依赖&#xff1a; [rootlocalhost ~]# yum install -y yum-utils device-mapper-persistent-data lvm2 wget //安装docker所需要的相关依赖 [rootlocalhost ~]#…

中国休闲装行业深度调研分析

环洋咨询Global Info Research的休闲装市场调研报告提供休闲装市场的基本概况&#xff0c;包括定义&#xff0c;分类&#xff0c;应用和产业链结构&#xff0c;同时还讨论发展政策和计划以及制造流程和成本结构&#xff0c;分析休闲装市场的发展现状与未来市场趋势&#xff0c;…

java入门-变量与常量

java 基本语法-变量与常量 变量 变量的本质 程序中我们会经常看到类似 int x 3**;** 的表达式&#xff0c;x就是我们常说的变量&#xff0c;从计算机角度我们来看看变量x的本质是什么&#xff1f; 在程序开发中定义一个变量x, 计算机会在内存中开辟内存空间&#xff0c;计算…

【C语言基础】:字符函数和字符串函数

文章目录 一、字符函数1. 字符分类函数2. 字符转化函数 二、字符串函数1. strlen函数的使用和模拟实现strlen函数的使用strlen函数的模拟实现 2. strcpy函数的使用和模拟实现strcpy函数的使用strcpy函数的模拟实现 3. strcat函数的使用和模拟实现strcat函数的使用strcat函数的模…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:Grid)

网格容器&#xff0c;由“行”和“列”分割的单元格所组成&#xff0c;通过指定“项目”所在的单元格做出各种各样的布局。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 仅支持GridItem…

MasterAlign视觉对位软件提示系统校准时间错误解决方案

MasterAlign视觉对位软件提示系统校准时间错误解决方案 一、问题现象 当运行软件时弹出“系统校准时间错误”的提示&#xff0c;如下图&#xff1a; 出现“系统校准时间错误”提示&#xff0c;说明当前系统时间比上一次软件运行时的系统时间提前了&#xff0c;需要修改当前系…

Windows系统搭建web网站并结合内网穿透实现公网访问本地站点

文章目录 使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点&#xff0c;测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中&#xff0c;查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2.2 映…

苹果MacOS电脑使用内网穿透轻松远程桌面本地Windows系统电脑

文章目录 1. 测试本地局域网内远程控制1.1 Windows打开远程桌面1.2 局域网远程控制windows 2. 测试Mac公网远程控制windows2.1 在windows电脑上安装cpolar2.2 Mac公网远程windows 3. 配置公网固定TCP地址 日常工作生活中&#xff0c;有时候会涉及到不同设备不同操作系统之间需要…

JetBrains全家桶激活,分享PyCharm 2024 激活的方案

大家好&#xff0c;欢迎来到金榜探云手&#xff01; PyCharm 公司简介 JetBrains 是一家专注于开发工具的软件公司&#xff0c;总部位于捷克。他们以提供强大的集成开发环境&#xff08;IDE&#xff09;而闻名&#xff0c;如 IntelliJ IDEA、PyCharm、和 WebStorm等。这些工具…

RP2040 VSCode C/C++开发环境快速部署

RP2040 VSCode C/C开发环境快速部署 &#x1f4cc;安装参考《树莓派(Raspberry Pi) Pico VSCode C/C开发环境配置(无需Visual Studio)》&#x1f4cd;Windows环境下 MSYS2一键式部署pico程序包&#xff0c;下载地址&#xff1a;https://github.com/raspberrypi/pico-setup-wind…

简单使用NSIS打包软件

NSIS是一个开源的打包工具. 官网: Download - NSIS (sourceforge.io) 使用这个编译 ​ 但是不建议使用这玩意写脚本,字体太难看了.我用vscode写的脚本,用这个编译的. ​ 写好脚本用这个软件打开, 然后选择这个编译,如果语法有错误 会编译不过,会提醒你哪一行不行,如果编译…

探讨NLP对行业大量数据信息抽取的技术实现

在本文中&#xff0c;为了实现高效的信息抽取&#xff0c;我们采用了一个自主研发的多模态AI的大模型NLP平台。 这个平台的使用过程分为以下几个步骤&#xff1a; 数据收集&#xff1a;我们收集了与项目相关的100条数据样本&#xff0c;这些样本涵盖了各种商品描述&#xff0c…

一口气看完明朝276年历史

明朝是中国历史上最后一个由汉人建立的大一统封建王朝&#xff0c;建立于公元1368年&#xff0c;亡于公元1644年&#xff0c;国祚276年&#xff0c;传12世16帝。 太祖建国 太祖&#xff08;1368~1398&#xff09; 公元1368年&#xff0c;朱元璋在南京应天府建元称帝&#xff…

多行业预约小程序源码系统:单多门店一键切换 带完整的安装教程以及安装代码包

在当今数字化时代&#xff0c;小程序以其便捷、高效的特点&#xff0c;成为企业连接用户、提升服务体验的重要工具。下面&#xff0c;罗峰给大家分享一款多行业预约小程序源码系统&#xff0c;该系统支持单多门店一键切换&#xff0c;并附带完整的安装教程及安装代码包&#xf…