关键词：
// greedy_algorithm.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<queue>
using namespace std;
#define NofActivity 11
int c[NofActivity + 1][NofActivity + 1];
int reme[NofActivity + 1][NofActivity + 1];
//活动的结构/////////////////////////////////////////
struct Activity
{
int num;
int start;
int finish;
};
Activity Act[12] = { {0,0,0},{ 1,1,4 },{2,3,5 },{3, 0,6 },{4, 5,7 },{5, 3,9 },{6, 5,9 },{7, 6,10 },{8, 8,11 },{9, 8,12 },{10, 2,14 },{11, 12,16 }};
///用队列来存储符合条件的活动，递归版本
queue<Activity> select;
void Recursive_activity_selector(Activity* Act, int k, int n)
{
int m = k + 1;
while (m <= n&&Act[m].start < Act[k].finish)
m++;
if (m <= n)
{
select.push(Act[m]);
Recursive_activity_selector(Act, m, n);
}
}
///活动选择的迭代版本//////////////////////
void Greedy_activity_selector(Activity* Act)
{
int n = NofActivity;
while (!select.empty())select.pop();
select.push(Act[1]);
int k = 1;
for (int i = 2; i <= n; i++)
{
if (Act[i].start > Act[k].finish) {
select.push(Act[i]);
k = i;
}
}
}
/////活动选择的动态规划版本//////////////////////////////////
void activity_selector(Activity* Act)
{
queue<int> que;
for (int i = 0; i <= NofActivity; i++)
{
c[i][i] = 0;
c[0][i] = 0;
c[i][0] = 0;
}
for(int l=2;l<=NofActivity;l++)
for (int i = 1; i <= NofActivity-l+1; i++)
{
int j = i + l - 1;
int m = i + 1;
while (m <= j&&Act[m].start < Act[i].finish)
m++;
if (m > j)c[i][j] = 0;
else
{
int temp = c[i][i];
reme[i][j] = i;
for(int k=i+1;k<=j;k++)
if (c[i][k] + c[k][j] + 1 > temp)
{
temp = c[i][k] + c[k][j] + 1;
reme[i][j] = k;
}
c[i][j] = temp;
}
}
}
int main()
{
//Recursive_activity_selector(Act, 0, NofActivity);
/*
Greedy_activity_selector(Act);
while (!select.empty())
{
cout << select.front().num<< ‘ ‘;
select.pop();
}
*/
activity_selector(Act);
for (int i = 1; i <= NofActivity; i++) {
for (int j = 1; j <= NofActivity; j++)
cout << c[i][j] << ‘ ‘;
cout << endl;
}
while (1);
return 0;
}
算法与程序设计：贪心算法
...子结构性质1.2贪心算法与动态规划算法的差异二、举例2.1活动安排问题2.2最优装载问题2.3哈夫曼编码一、概念1.1贪心算法的基本要素贪心选择性质最优子结构性质1.1.1贪心选择性质1.1.2最优子结构性质1.2贪心算法与动态规划算法... 查看详情
活动安排问题-贪心算法
贪心算法：贪心算法总是做出在当前看来最好的选择，也就是贪心算法不从整体最优化的角度考虑。它所做出的选择只是在某种意义上的局部最优选择性质：最优子结构性质当一个问题的最优解包含其子问题的最优解... 查看详情
贪心算法-活动安排问题(代码片段)
活动安排问题问题描述有n个需要使用同一资源的活动，且在同一时段只有一个活动能使用该资源。每个活动i都有一个起始时间si和结束时间fi，且si<ei。如果选择了活动i，则它在半开时间区间[si，ei)内占用资源。若区间[si，ei)... 查看详情
《算法导论》读书笔记
...过所做的局部最优选择来产生一个全局最优解。书中先从活动选择问题来引入贪心算法，分别采用动态规划方法和贪心算法进行分析。本篇笔记给出活动选择问题的详细分析过程，并给出详细的实现代码进行测试验证。关于贪心... 查看详情
动态规划与贪心算法_剪绳子问题(代码片段)
...题的最解2.贪婪算法求解：每一步都可以做出一个贪婪的选择，基于这个选择，确定能够得到最优解1． 贪心算法在对问题求解时，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解2． 选择的贪心策略... 查看详情
贪心算法(代码片段)
...）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪... 查看详情
动态规划算法学习总结(代码片段)
...贪心、分治的区别贪心算法(Greedalalgorithm)是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致全局结果是最好或最优的算法。分治算法(Divideandconqueralalgorithm)字面上的解释是“分而治之”，... 查看详情
算法导论笔记——第十六章贪心算法
...求得最优解，而且速度比动态规划方法快得多。 16.1活动选择问题按结束时间排序，然后选择兼容活动。定理16.1考虑任意非空子问题Sk，令am是Sk中结束时间最早的活动，则am在Sk的某个最大兼容活动子集中。 16.2贪心算法... 查看详情
python_分治算法贪心算法动态规划算法(代码片段)
...思想2、寻找假币示例二、贪心算法1、思想2、最大不相容活动安排示例三、动态规划1、思想2、最大和路径3、背包问题4、动态规划和贪心算法的区别一、分治算法思想分治算法是一种化繁为简的算法思想。分治算法往往应用于... 查看详情
贪心算法和动态规划的区别与联系
....都是分解成子问题来求解，都需要具有最优子结构区别1.贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，... 查看详情
背包问题（贪心算法）(代码片段)
...划算法的区别：贪心算法两个最重要的性质：（1）贪心选择性质；（2）最优子结构性质；其中，贪心选择性质：自顶向下进行决策，每次做出的决策都是局部最优解，且每次做出决策后问题规模都变小了；最优子结构性质：即... 查看详情
分治法动态规划贪心算法区别
1.分治法算法思想：将原问题划分成若干个规模较小而结构与原问题相似的子问题，递归的解决这些子问题，然后再合其结果，就得到原问题的解特征：该问题的规模缩小到一定的程度就很容易解决该问题可以分解为若干个规模... 查看详情
贪心算法
...化问题的算法一般包含一系列的步骤，每一步都有若干的选择。对于很多最优化问题，只需要采用简单的贪心算法就可以解决，而不需要采用动态规划方法。贪心算法使所做的局部选择看起来都是当前最佳的，通过局部的最优化... 查看详情
五类常见算法小记（递归与分治，动态规划，贪心，回溯，分支界限法）
近日复习了一些算法知识，小记于此递归与分治法直接或间接地调用自身的算法称为递归算法。递归是算法设计与分析中经常使用的一种技术，描写叙述简单且易于理解。分治法的设计思想是将一个规模为n难以解决的问题分解... 查看详情
动态规划算法介绍，以及和贪心算法的比较(代码片段)
##问题描述：1.什么是动态规划算法2.动态规划算法为何能带来效率上的提升3.动态规划算法的特征 ##解决方案：问题1：什么是动态规划算法回答：大约在60多年前，动态规划算法开始出现并大规模使用，动态规划算法的英文... 查看详情
算法设计与分析报告
...。也可以理解贪心算法并不是从总体上考虑，它所做出的选择只是在某种意义上的局部最优解 查看详情
习题—动态规划贪心算法(代码片段)
算法导论第15、16章习题—动态规划、贪心算法1.我们对钢条切割问题进行一点修改，除了切割下的钢条段具有不同价格pip_ipi外，每次切割还要付出固定的成本ccc。这样，切割方案的收益就等于钢条段的价格之和减... 查看详情
程序员算法基础——贪心算法
...化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。能用贪心解决的问题，也可以用动态规划解决。而广义的贪心... 查看详情