关键词：
贪心算法：贪心算法总是做出在当前看来最好的选择，也就是贪心算法不从整体最优化的角度考虑。它所做出的选择只是在某种意义上的局部最优选择
性质：最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质
与动态规划的差异：
贪心算法从局部出发，每一次得到的最优解，在考虑求解最优解的时候沿用上一次的最优解，之前的最优解不做保留。
动态规划从全局出发，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。
经典贪心算法，例如： 图的单源最短路径问题，最小生成树问题
活动安排问题
例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
package com.arithmetic.interview;
/**
* Created by leiqiao on 2017/11/3.
* 设有n个活动的集合E=1,2,…,n，其中每个活动都要求使用同一资源，
* 如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
* 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi。
* 如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,
* 则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。
* 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
*/
public class test04_huodonganpai
private static int [] s = 1,3,0,5,3,5,6,8,8,2,12;
private static int [] f = 4,5,6,7,8,9,10,11,12,13,14;
private static int countLength = 11;
private static boolean a[] = new boolean[countLength];
public static int greedySelector(int s[], int f[], boolean [] a)
//数学归纳法得出最优解一定包含第一个活动，
//且需要注意的是，活动的结束时间升序
int activityIndex = 0;
a[activityIndex] = true;
int activityCount = 1;
for (int i = 1; i < countLength; i++)
if(s[i] > f[activityIndex])
activityIndex = i;
a[i] = true;
activityCount++;
return activityCount;
public static void main(String [] args)
System.out.println(greedySelector(s, f, a));
for(int i = 0; i < a.length; i++)
if(a[i])
System.out.println("活动" + (i+1) + " ");
c++算法主题系列之贪心算法的贪心之术(代码片段)
...。本文将通过几个案例深入探讨贪心算法的贪心策略。2.活动安排问题问题描述：有n个活动a1,a2,…,an……需要在同一天使用同一个教室，且教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi。一个活... 查看详情
c_cpp【贪心算法】活动安排问题(代码片段)
算法与程序设计：贪心算法
...子结构性质1.2贪心算法与动态规划算法的差异二、举例2.1活动安排问题2.2最优装载问题2.3哈夫曼编码一、概念1.1贪心算法的基本要素贪心选择性质最优子结构性质1.1.1贪心选择性质1.1.2最优子结构性质1.2贪心算法与动态规划算法... 查看详情
算法导论笔记——第十六章贪心算法
通常用于最优化问题，我们做出一组选择来达到最优解。每步都追求局部最优。对很多问题都能求得最优解，而且速度比动态规划方法快得多。 16.1活动选择问题按结束时间排序，然后选择兼容活动。定理16.1考虑任意非空子... 查看详情
（转）贪心算法之精辟
问题一、活动安排问题问题表述：设有n个活动的集合E = {1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活i都有一个要求使用该资源的起始时间si和一个... 查看详情
数据结构与算法笔记（十七）——贪心算法及经典案例(找零问题背包问题拼接最大数字问题活动选择问题)(代码片段)
一、贪心算法贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法并不保证会得到最优... 查看详情
数据结构与算法笔记（十七）——贪心算法及经典案例(找零问题背包问题拼接最大数字问题活动选择问题)(代码片段)
一、贪心算法贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法并不保证会得到最优... 查看详情
贪心算法-第一节：贪心算法概述(代码片段)
...题目描述②：解题思路③：完整代码（2）活动安排问题①：题目描述②：解题思 查看详情
贪心算法-活动安排问题(代码片段)
活动安排问题问题描述有n个需要使用同一资源的活动，且在同一时段只有一个活动能使用该资源。每个活动i都有一个起始时间si和结束时间fi，且si<ei。如果选择了活动i，则它在半开时间区间[si，ei)内占用资源。若区间[si，ei)... 查看详情
《算法导论》读书笔记
前言：贪心算法也是用来解决最优化问题，将一个问题分成子问题，在现在子问题最优解的时，选择当前看起来是最优的解，期望通过所做的局部最优选择来产生一个全局最优解。书中先从活动选择问题来引入贪心算法，分... 查看详情
python_分治算法贪心算法动态规划算法(代码片段)
...思想2、寻找假币示例二、贪心算法1、思想2、最大不相容活动安排示例三、动态规划1、思想2、最大和路径3、背包问题4、动态规划和贪心算法的区别一、分治算法思想分治算法是一种化繁为简的算法思想。分治算法往往应用于... 查看详情
贪心算法回溯算法(代码片段)
...问题化简为一个更小的与原问题具有相同形式的子问题。活动安排问题回溯算法应用回溯法求解时，需要明确定义问题的解空间。旅行商问题–>使用排列数解决。用约束函数在扩展结点处剪去不满足约束条件的子树；... 查看详情
五大常用算法之三贪心算法
...最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。 贪心算法每一步必须满足一下条件： 1、可行的：即它必须满足问题的约束。 2、局部最优：他是当前步骤中所有可行选择中最佳的... 查看详情
hdu2037今年暑假不ac（贪心）
...心）题目：http://acm.hdu.edu.cn/showproblem.php?pid=2037很经典的活动安排问题变形，与算法教材的活动安排一样，依据结束时间进行排序，然后相容的累加就可以。//经典贪心问题活动时间安排的简单变形//按活动结束时间，递增排序，... 查看详情
活动选择的贪心算法与动态规划（未完成）
//greedy_algorithm.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#include<iostream>#include<queue>usingnamespacestd;#defineNofActivity11intc[NofActivity+1][NofActivity+1];intreme[NofActivity+1][No 查看详情
贪心算法舞蹈室的安排
描述：新活有个舞蹈室，并且只有一个舞蹈室，假设申请时间以小时为单位，每天24个小时，每周就是168小时，我们规定申请时间从每周一的0点开始递增，比如申请时间区间为【1，24】就代表周一的0点到24点，时间区间【25，48... 查看详情
贪心算法(贪婪算法)(代码片段)
...字符串买卖股票的最佳时机跳跃游戏钱币找零多机器调度问题举办活动数量最多无重叠区间贪心算法思想1.贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，... 查看详情
expm7_2区间调度问题
【问题描述】给定n个活动，其中的每个活动ai包含一个起始时间si与结束时间fi。设计与实现算法从n个活动中找出一个最大的相互兼容的活动子集S。要求：分别设计动态规划与贪心算法求解该问题。其中，对贪心算法分别给... 查看详情