贪心算法几个经典例子
答:物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析:目标函数:∑pi最大 约束条件是装入的物品总重量不超过背包容量,即∑wi<=M( M=150)(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?(2)每次挑选所占重量最...
答:贪心算法经典例子如下:活动安排问题是可以用贪心算法有效求解的一个很好的例子,该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合e=(1,2,…,n),其中每个活动都要求使用同一资源,如演讲会场等,...
答:如果根据贪心算法的话,我们上来肯定是看需要几张20的,这道题需要1张,那还剩36-20=16。看完20的我们再来看10元的,需要1张10元,现在还剩16-10=6。下面继续是看5和1,分别就需要1张。最后我们得到的答案是,如果想要凑齐36元我们最少需要4张纸币。这个例子,每次都是用最大的纸币去匹配,剩...
答:下面看一个例子: 假如我们有一个包含1000个字符的文件,每个字符占1个byte(1byte=8bits),则存储这100个字符一共需要8000bits。这还是有一些大的 那我们统计一下这1000个字符中总共有多少种字符,原来需要8bit来表示一个字符,如果使用更少的位数来表示这些字符,则可以减少存储空间。 假设这...
答:求解一个问题时有多个步骤,每个步骤都选择当下最优的那个解,而不用考虑整体的最优解。通常,当我们面对的问题拥有以下特点的时候,就可以考虑使用贪心算法。比如,我们举个例子,仓库里面总共有五种豆子,其对应的重量和总价值如下,现在我们有一个可以装100KG重量的袋子,怎么装才能使得袋子中的豆子...
答:根据常识,我们到店里买东西找钱时,老板总是先给我们最大面值的,要是不够再找面值小一点的,直到找满为止。如果老板都给你找分数的或者几角的,那你肯定不干,另外,他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。问题的算法设计与实现:先举个例子,假如老板要找给我99...
答:因为这个问题涉及到高维求解(大于3维),所以不推荐你用贪心算法或遗传算法之类的算法。这里给出一种升级的蒙特卡罗算法——自适应序贯数论算法,这是一种以GLP集合为基础的随机遍历算法,可以很轻易的解决一系列的高维求解问题,目前根据网上能找到的资料最多可以做到18维。下面就根据你给出的例子讲解一下:对于6000的料来...
答:由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了。 话不多说,我们来看几个具体的例子慢慢理解它: 1.活动选择问题 这是《算法导论》上的例子,也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an,教室同一时刻只能由一...
答:插入排序的工作方式是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这个过程就是贪心选择的过程,每次选择都是在当前状态下最好的选择,也就是将未排序元素插入到已排序序列的正确位置。举个例子,假设我们有一个无序数组 [5, 3, 6, 7, 1],插入排序的过程...
答:则上一步往该格子走 B)如果仍旧都有或都没有,重复2)直到找到符合A)的情形。假设棋盘是N*N个格子,则贪心算法最坏的情形是要遍历整个棋盘,比如只有第一个格子有金块时,就需要遍历整个棋盘才能确定走法。最好的情形也需要遍历4*N个格子。时间复杂度上来算的话,应该是O(nLogn)...
网友评论:
冶夜15037157267:
给我讲一下贪心算法吧,网上看过,还是不太懂,我是高一的...请给出一个通熟易懂的例子吧,最好有源码 -
8583能程
: 最经典的一个例子就是背包问题,建议你还是多理解一下,算法 就像数学一样,自己必须理解了才行,贪心算法用于的地方 很多很多,所以靠不了别人滴,简单理解就是每次从集合中选最好的,选择了 就不用考虑,一直到最后,一般程序使用递归实现
冶夜15037157267:
贪心法的应用算法有哪些?
8583能程
: 如果觉的我答案有用,请点赞. 贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式所以需要说明的是,贪心算法可以与随机化算法一起使用,具体的例子就不再多举了
冶夜15037157267:
哪些常见算法属于贪婪算法 -
8583能程
: 是贪心算法吧…… 就是每次都取最优值...比如合并果子: 有n堆果子,每个果子都有一个重量,每次可以任意选择2堆果子将其合并成一堆,花费是这两堆果子的重量值之和,求最终合并成一堆的最小(最大)花费. 算法就是,每次取重量最小(最大)的两堆果子合并,直到还剩一堆.
冶夜15037157267:
几种常用的算法简介 -
8583能程
: 1、穷举法穷举法是最基本的算法设计策略,其思想是列举出问题所有的可能解,逐一进行判别,找出满足条件的解. 穷举法的运用关键在于解决两个问题: 在运用穷举法时,容易出现的问题是可能解过多,导致算法效率很低,这就需要对列举...
冶夜15037157267:
贪心算法的例题分析是什么呢?
8583能程
: 对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:⑴贪心策略:选取价值最大者
冶夜15037157267:
c语言问题急!!!(用贪心算法) -
8583能程
: 题分析:根据常识,我们到店里买东西找钱时,老板总是先给我们最大面值的,要是不够再找面值小一点的,直到找满为止.如果老板都给你找分数的或者几角的,那你肯定不干,另外,他也可能没有那么多零碎的钱给你找.其实这就是一个...
冶夜15037157267:
贪心算法 动态规划 它们有什么区别?程序设计 -
8583能程
: 贪心算法是种策略,思想...它并没有固定的模式 比如最简单的背包问题 用贪心的思想去做,就可能有很多种方法 性价比最高的、价值最高的、重量最轻的 而你没办法确保你所选择的贪心策略对所有的情况都是绝对最优的 动态规划的思想是分治+解决沉余 把一个复杂的问题分解成一块一块的小问题 每一个小问题中得到最优解 再从这些最优解中获取更优的答案 典型的例子数塔问题 画个图就能看出来
冶夜15037157267:
背包问题贪心算法 -
8583能程
: 可以打乱顺序乱贪.可以用模拟退火,神经网络这样的算法找近似值.目前背包问题还没用多项式时间内的解法.
冶夜15037157267:
求背包问题贪心算法实例结果
8583能程
: 找零钱问题:以人民币1元,2元,5元,10元,20元,50元,100元为例,要求所找的张数最少 背包问题:假设物体重量W1,W2...Wn其对应的价值为P1,P2...Pn,物体可分割,求装入重量限制为m的背包中的物体价值最大.可用P/W来解答. #...
冶夜15037157267:
找零钱问题的贪心算法 -
8583能程
: 你已经给出了算法,还要什么算法?你又不说是什么语言.只好把编程思想给你:比如要找N分钱,先拿N除最大零钱面值,可以取模得出余数.当然取整就是所找的最大面值零钱的个数.所得余数再次处理,用的是一个循环结构.明白了吗?N输入取值 M是定义的面值M[0]是最大面值 K是一个数组,存储各面值零钱的个数 i=0 do while (N>0) K[0]=int(N/M[i]) N=mod(N,M[i]) i++ end do