贪心和动规的difference

2024-03-20 00:18
文章标签 贪心 difference 动规

本文主要是介绍贪心和动规的difference,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

很多同学在做动规题的时候,很容易做成贪心,的确,动规和贪心是很相近的,在很多时候,动规和贪心没有明显的界限,反而在很多时候,我们需要使用贪心的思想,对动规进行优化,不过这也就导致了很多同学分不清什么题是动规,什么题是贪心。    

现在我们来回忆一下,动规的思想是什么,以前一个或者多个状态的最优值,加上现在这个状态的最优解,在其中取得当前的最优解,再层层递推,得到最终答案。    

那么贪心呢?贪心的思想是由局部的最优解进行组合,使用分治的思想,局部的最优解组合起来就得到了总得最优解。   

 仔细对比两种思想,你发现两者之间有什么差别了吗?

没错,在贪心中,每一个局部的最优解之间是没有任何联系的,我们可以分开同时求解,而在动态规划中,我们必须要应用前面的阶段中的最优值,才可以得到当前的最优值。  

所以在区别动归和贪心的时候,关键就是:我们在得到当前最优解的时候,需不需要使用前面的阶段中的得到的值,如果不需要,那就是贪心;如果需要,就是动归。    下面我举一道题来说明,这是非常基础的一道题,每一个人都见过,数字三角形。    现在有一个数字三角形,我们从最上方走到最下方。比如下面这个数字三角形  

        7 

      3  8 

    8  1  0 

  2  7  4  4 

4  5  2  6  5  

如果我不给出一个点只能走到左下或者右下这个限制条件,我们可以从这一层的一个点走到下一层的任意一个点,那么我们发现这道题就是一个很简单的贪心,取出每一排的最大的数字相加就是我们的和。 如果加上了那个条件呢???  那么我们就必须使用动态规划,方程很简单f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];  为什么加上一个条件后,就变成了动态规划呢??   因为我们加上了这个条件之后,我们走到当前这一个层的时候,

受到了前面走到的节点的限制,我们必须要依赖于前面走到的节点,才能够走到当前的节点,所以这道题就不是贪心,而是动归。  贪心可以保证一次最优,而动规可以保证整体最优,   大家清楚了吗?   接下来有一句话,送给喜欢贪心的同学:贪心不能解决动归,动归可以解决贪心。   


最后我们来回忆一下当初同学们都以为是贪心的一道题,田忌赛马:  


田忌赛马    

【问题描述】  中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了,他们各派出N匹马,每场比赛,输的一方将要给赢的一方200两黄金,如果是平局的话,双方都不必拿出钱。现在每匹马的速度值是固定而且已知的,而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马,才能赢取最多的钱?  

【输入格式】   第一行为一个正整数n (n <= 2000) ,表示双方马的数量。 第二行有N个整数表示田忌的马的速度。 第三行的N个整数为齐王的马的速度。  

【输出格式】  仅有一行,为田忌赛马可能赢得的最多的钱,结果有可能为负。 

【输入样例】  

92 83 71 

95 87 74 

【输出样例】  

200  


 当初同学们在思考这道题的时候大都认为这是一道贪心,自己的马如果能胜,就用最大的一匹取胜,如果不能,就用最差的那匹取输,这种思想看似有理,但是有一个很简单的道理,存在平局。  所以赢得多,可能输得越多,赢得少,可能输得少。  所以,简单的相加不能够得到我们的最优解,我们发现这种策略存在明显的动态规划特征。  

由于齐王的马的出场顺序是确定的,所以前面的马的安排不会影响到后面的对决,前面得到的最优解加上现在对决的最优解就是当前的最优解,最优子问题,无后效性,都存在,所以这一定是一道动规。  线性?区间?背包?   很明显,这是一道区间的问题,i到j这一个区间的最优值是不是其中的一匹马去对战齐王的第j-i匹马的结果加上剩下的马去对战齐王的j-i-1匹马的最大值的最大值。    那么贪心就完全没用了吗???   我说过贪心可以优化动规,因为动规本来就满足最优子问题结构,使用贪心的思想,在求最优子问题的时候,可以省下不少的时间. 

   在这道题中,当我们在i到j这个区间内选派马去和齐王的j-i这匹马对战的时候,我们使用前面得到的贪心策略, 1. 用最大的马 2. 用最小的马  我说过,贪心在一次的决策中可以保证是最优的  所以无论如何,这样的策略在这一次决策中一定是最优的,这样我们就使用贪心策略清楚地解决了动规的最优子问题。  f[i][j]代表田忌的第i到第j匹马对战齐王的前j-i匹马得到的最大值.  F[i][j]=max{f[i+1][j]+cost[i][j-i],f[i][j-1]+a[j][j-i]};   


最后再次重申一句话:  贪心是局部的最优解,动规是整体的最优解

这篇关于贪心和动规的difference的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/827679

相关文章

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

ural 1820. Ural Steaks 贪心

1820. Ural Steaks Time limit: 0.5 second Memory limit: 64 MB After the personal contest, happy but hungry programmers dropped into the restaurant “Ural Steaks” and ordered  n specialty steaks

ural 1014. Product of Digits贪心

1014. Product of Digits Time limit: 1.0 second Memory limit: 64 MB Your task is to find the minimal positive integer number  Q so that the product of digits of  Q is exactly equal to  N. Inpu

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

BUYING FEED(贪心+树状动态规划)

BUYING FEED 时间限制: 3000 ms  |  内存限制: 65535 KB 难度:4 描述 Farmer John needs to travel to town to pick up K (1 <= K <= 100)pounds of feed. Driving D miles with K pounds of feed in his truck costs D

vua 10700-Camel trading 贪心以及栈

大意:给一个表达式,可以让你任意套括号,问套完括号最大最小值是多少 贪心策略:最大的话,先+后*                  最小的话,先*后+ 用了一个栈堆模拟运算的次序 #include<stdio.h>#include<iostream>#include<stack>using namespace std;int main(){int N;scanf("%d",&

Commando War-uva 贪心

大意:给你N个任务,你交代他需要J时间,完成他需要B时间,问怎么搭配可以使全部问题完成时话的时间最少 思路:贪心算法,先做完成时间长的,完成时间相同的话先做交代时间长的,用了一下结构体二级快排 #include<stdio.h>#include<string.h>#include<stdlib.h>#define MAX_SIZE 1000 + 10struct Time{int