代码编织梦想

简介:贪心算法顾名思义就是比较比较贪心的一个算法,思路就是要贪。做的选择每一步都是最贪的。

例题:你提着一个袋子去买米,正好米店做活动,给你免单,但是只能用你自己的袋子装。米店里有三种米,分别是 白米,黑米,紫米,假设三种米价值分别为2元一斤,3元一斤,4元一斤,你的袋子可以装20斤,但是由于你来的太晚了,三种米分别只剩下15斤,10斤,4斤,那么你怎么装才能让你装的米,价值最大。

解析:很显然,我们应该先挑贵的装,这才符合我们贪心的想法。贵的紫米只有4斤,装完紫米,还有空位,这时候就去装黑米,装完黑米还有空位,这时候就去装白米,直到装不下了。

伪代码:

  value[3],weight[3],cap=20,money=0,;//三种米的价值value,剩余数量weight,袋子容量cap,装了的米的价值money;

    sort(value,weight);//将米的价值按高到低排好序,同时米的剩余数量对应好,

 for(i=0;i<3;i++)//循环遍历米的价值数组 如果袋子还有容量,就装米,如果袋子容量小于这种米数量,那就只装剩下容量的数量。如果没有空位了,推出循环。

 if(cap>0)

    if(cap>=weight[i])

       {money+=weight[i]*value[i];

        cap=cap-weight[i]}

    else  {

      money+=cap*value[i];

     cap=0;}

 else break;

01背包问题:进阶思考:

买米换成买水果,袋子变成10斤,水果为苹果,香蕉,菠萝,三种水果每种只有1个,重量分别为

4,5,7 ,价值分别为 4,5,8;水果不可切开,请问如果装水果才能价值最大化。

未完待续:

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sensern/article/details/127972485

从零开始学贪心算法-爱代码爱编程

本文在写作过程中参考了大量资料,不能一一列举,还请见谅。 贪心算法的定义: 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关

一种基于贪心选择策略的哈夫曼算法_qq_39261315的博客-爱代码爱编程

摘要 当一个问题具有最优子结构性质时,可用动态规划法求解,但有时会有更简单,更有效的算法。本文通过对哈夫曼编码问题的引入,探讨并研究了贪心算法的基本思想及其特点,并在这一典型的贪心算法的基础上推广到三元码的情形,证明该算法是否可产生最优三元码。 关键词 贪心算法,贪心选择性质,最优子结构性质,哈夫曼算法,三元码   1问题简述 哈夫曼编码是广泛地用于数据文

从零开始学贪心算法(转载)_lanyu_01的博客-爱代码爱编程_从零开始学贪心算法

文章来源:https://blog.csdn.net/qq_32400847/article/details/51336300 本文在写作过程中参考了大量资料,不能一一列举,还请见谅。 贪心算法的定义: 贪心算法是

六中常用算法设计:穷举法、分治法、动态规划、贪心法、回溯法和分支限界法_岩枭的博客-爱代码爱编程

算法设计之六种常用算法设计方法 1.直接遍历态(穷举法)        程序运行状态是可以遍历的,遍历算法执行每一个状态,最终会找到一个最优的可行解;适用于解决极小规模或者复杂度线性增长,而线性规模不会很大的状态。 2.分治法       将一个难以直接解决的大问题,分割成一些规模较小的相同小问题,以便各个击破,分而治之。 思想策略:    

分治,贪心,回溯,动态规划算法的简要理解_fighting++++的博客-爱代码爱编程

好久没更新博客,都长草了!!! 1.动态规划 动态规划通俗来讲就是一种分阶段解决问题的数学思想。如电视剧中佛门中人经常提及的一个思想:大事化小,小事化了。 举例如下: 有一座高度是10级台阶的楼梯,从下往上走,每跨一步

贪心算法(文字描述解释)-爱代码爱编程

贪心算法 ​ 贪心算法(又称贪婪算法,greedy algorithm)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解,而不能算是全局最优解。它的性质是一种改进了的分级处理方法,核心是根据题意选取一种量度标准,贪心算法在解决问题的时候还要考虑其正确性。 ​ 贪心算法不是对所有

10.6 贪心算法详解及LeetCode题目-爱代码爱编程

可参考几篇博客 详解贪心算法(Python实现贪心算法典型例题) 五大常用算法之一:贪心算法   算法概述 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无

贪心算法的证明题-爱代码爱编程

贪心算法的证明一般是比动态规划要复杂。 原因是贪心算法的证明有两个,一个是最优子结构,另外一个是贪心选择性质。贪心选择性质: 可以通过局部最优选择来构造全局最优解 证明:一般考虑某个子问题的最优解,然后考虑用一个贪心选择替换其中某个选择,修改此解,导出更小子问题。 最优子结构同动态规划,而且其实一般也不是特别需要证明,关键还是在证明问题具有贪心选择性质,下

算法分析与设计实验报告二——贪心算法实验-爱代码爱编程

一、实验目的 了解贪心算法思想掌握贪心法典型问题,如背包问题、作业调度问题等。二、实验内容 编写一个简单的程序,实现单源最短路径问题。编写一段程序,实现找零。 【问题描述】当前有面值分别为2角5分,1角,5分,1分的硬币,请给出找n分钱的最佳方案(要求找出的硬币数目最少)。编写程序实现多机调度问题 【问题描述】要求给出一种作业调度方案,使所给的n个作业

C语言最常用的贪心算法就这么被攻克了-爱代码爱编程

来源:大鱼机器人 01 基本概念 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。 贪心算法没有固

python贪心算法_[Python]贪心算法-Prim-和-Kruskal实现-最小生成树-爱代码爱编程

目标 在连通网的所有生成树中,找到所有边的代价和最小的生成树,简称最小生成树问题. (简要的来说,就是在AOV网中找出串联n个顶点代价总和最小的边集) 下面记录最小生成树的两种算法,Prim和Kruskal Prim算法思路 从任意一个顶点开始,每次选择与当前顶点最近的一个顶点,并将两点之间的边加入到树中 被选中的点构成一个集合,剩下的点是

贪心算法--猫粮换咖啡豆-爱代码爱编程

FatMouse’ Trade Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 54406 Accepted Submission(s): 18244 Problem Description FatM

(C++附代码!)哈夫曼编码(贪心算法)-爱代码爱编程

(C++附代码!)哈夫曼编码(贪心算法) 一、问题描述 【问题描述】使用贪心算法求解Huffman编码问题,具体来说就是,根据每个字符的出现频率, 使用最小堆构造最小优先队列,构造出字符的最优二进制表示,即前缀码。在程序开始说明部分, 简要描述使用贪心算法求解Huffman编码问题的算法过程。 【输入形式】在屏幕上输入字符个数和每个字符的频率。

算法-贪心算法知识总结-爱代码爱编程

目录 1.要素 2.步骤 3.应用实例 4.反例 1.要素 (1)贪心选择性质 贪心选择性质是指,所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。 我们来对贪心算法和动态规划算法做一个对比。  在动态规划算法中,每步所做的选择往往依赖于相关

贪心算法在计算机体系结构中的应用_用贪心算法设计一个具有学习能力的智能系统-爱代码爱编程

目录 一.前言 二.离线缓存(Offline caching) 1.高速缓存技术的简要介绍 2.问题引入 3.精确问题,寻找思路 4.引入贪心算法 5.最优子结构性质的证明 (1)变量准备  (2)反证法证明(“cut-paste”法) 6.递推表达式设计 7.贪心性质的证明(很麻烦)  三.贪心策略在计算机底层的其他应用 1