贪心算法贪心算法和动态规划有什么区别？

c++ 贪心算法求解

#include<iostream.h> #define N 1000 typedef struct work { int day; int point; }work; int Fun(work a[]) { int i,j=0,count=0,day;work mid; for(i=0;i<N&&a[i+1].day>0;i++)//循环将期限小的排在前面，若期限相同，则将扣分多的排在前面 { if(a[i].day>a[i+1].day) {mid=a[i]; a[i]=a[i+1]; a[i+1]=mid; } if(a[i].day==a[i+1].day) { if(a[i].point<a[i+1].point) { mid.point=a[i].point; a[i].point=a[i+1].point; a[i+1].point=mid.point; } } } for(i=0,day=1;a[i].day>0;i++,day++)//计算扣的分数 {

if(a[i].day<day) count=count+a[i].point; } return count; } void main() { int i,j,T,n,b[N];work a[N]; cin>>T; for(i=0;i<T;i++) { cin>>n; for(j=0;j<n;j++) cin>>a[j].day; for(j=0;j<n;j++) cin>>a[j].point; b[i]=Fun(a); } for(i=0;i<T;i++) cout<<b[i]; }

能用贪心算法求解的问题应该具备哪些条件

贪心算法是种策略，思想。

。

。

它并没有固定的模式比如最简单的背包问题用贪心的思想去做，就可能有很多种方法性价比最高的、价值最高的、重量最轻的而你没办法确保你所选择的贪心策略对所有的情况都是绝对最优的动态规划的思想是分治+解决沉余把一个复杂的问题分解成一块一块的小问题每一个小问题中得到最优解再从这些最优解中获取更优的答案典型的例子数塔问题画个图就能看出来

5.贪心算法的核心思想。6.什么是递归？什么是迭代？两者的区别，举例说明。7.回溯的含义是什么？举例

1、贪心算法主要是把问题分成很多局部问题，用局部最优解合成整体最优解。

因此使用这种算法需要此问题满足两个条件，一个是能够分成多个能够求解的局部问题，第二个就是局部问题的解能够合成最优解。

和动态规划、回溯等相比差别就是再不回溯的前提下找出整体最优解或者接近最优解，速度快但应用有比较大的限制。

2、迭代也叫递推，通过重复执行某一步骤或者函数来求得计算结果 递归是指函数中直接或者间接调用自身 举例： 求a乘以2的10次方等于几 迭代： for (i=0;i<10;i++) a *= 2; 递归： int db(int a,int num) { if (num<10) return 2 * db(a,num+1); else return 1; } db(a,0); 3、回溯的含义就是在搜索问题的状态过程中，如果不能继续前进，再向后回到岔口，换一条路继续搜索，直到搜索完所有状态或者查找到需要的状态。

举例：（最典型的就是树的深度搜索，下面举一个简单的例子） int a[10]={5,3,7,9,3,2,5,6,9,1};//从3开始查找1 int read[10]=(0);//是否查找过 int readNum = 0;//查找过的个数 int forward = 1;//1为左，2为右 int tmp = 0,index = 5; tmp = a[index]; read[index] = 1; readNum++; while (tmp != 1 || readNum != 10) { if (forward == 1) index --; else index++; if (!read[index]) { tmp = a[index]; read[index] = 1; readNum++; } if (index <=0 || index>=9) forward = 3 - forward; }

编程中什么是贪心算法

贪心策略是：指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。

其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。

找零钱问题的贪心算法

问题描述： 当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少） 问题分析： 根据常识，我们到店里买东西找钱时，老板总是先给我们最百大面值的，要是不够再找面值小一点的，直到找满为止。

如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。

其实度这就是一个典型的贪心选择问题。

问题的算法设计与实现： 先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99／25＝专3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分，由于还少给我24，所以还得给我2个10分的和4个1分。

具体实现 //找零钱算法 //By falcon //输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分 //输出：数组num，对照数组m中的面值存属放不同面值的硬币的个数，即找钱方案

贪心算法和动态规划有什么区别？

动态规划和贪心算法都是一种递推算法 均有局部最优解来推导全局最优解 不同点： 贪心算法： 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。

2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法： 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解 3.边界条件：即最简单的，可以直接得出的局部最优解 注：给我你电子邮箱，我把详细资料发过去