算法之路 直奔贪心
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法之路 直奔贪心,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3360字,纯文字阅读大概需要5分钟。
内容图文
活动选择问题
- 引言
三月份开始了,各种笔试面试接踵而至,淡定淡定呀。。。
- 题目
给出一组活动,其中每个活动都有一个开始时间和一个结束。给你一个总的时间区间,然后可以容纳的最多的活动组合。(选自算法圣经)
- 思路
本题目是贪心的例题1,切记贪心的答案不一定是最优的。本题目的解法使用贪心,缩小问题的规模,直至问题规模缩小至不能在缩小为止。
题目解法 递归解法
// function: 递归 void ActivitiesChoices::PECURSIVE_ACTIVITY_SELECTOR( int i ,int n ) { int m = i + 1 ; while( m<=n && s[m]<f[i] ) m = m+1 ; if( m <= n ) { Result->push_front(m) ; this->PECURSIVE_ACTIVITY_SELECTOR(m,n) ; } }
非递归解法
// function: 非递归 void ActivitiesChoices::GREEDY_ACTIVITY_SELECTOR( ) { Result->clear(); Result->push_front(1); int i =1 ; int m ; for( m = 2 ; m <= size ; m++ ) { if( s[m]>=f[i] ) { Result->push_front(m) ; i = m ; } } }
弊端:没有求出所有的答案,答案不全。
- 实验
- 代码
test.cpp#include <iostream> #include <list> #include <fstream> using namespace std ; int const size = 11 ; class ActivitiesChoices { int * s ; int * f ; list<int> * Result; public: ActivitiesChoices( void ) ; void SF_time_read( ) ; void SF_time_set( ) ; void PECURSIVE_ACTIVITY_SELECTOR( int i ,int n ) ; void GREEDY_ACTIVITY_SELECTOR(); void Result_Show( ) ; void Main( ) ; ~ActivitiesChoices( void ) ; }; ActivitiesChoices::ActivitiesChoices(void) { s = new int[size+1] ; f = new int[size+1] ; Result =new list<int>; } void ActivitiesChoices::SF_time_set( ) { int a[12]={0,1,3,0,5,3,5,6,8,8,2,12}; int b[12]={0,4,5,6,7,8,9,10,11,12,13,14}; ofstream fileWriter ; fileWriter.open("data.txt") ; fileWriter.clear(); int i = 1 ; fileWriter<<‘S‘; //fileWriter<<‘\n‘;// 2 个字符 while( i <= size ) { fileWriter<<a[i]; fileWriter<<‘-‘; i++; } i = 1; fileWriter<<‘\n‘; // 3 个字符 fileWriter<<‘F‘; //fileWriter<<‘\n‘; while(i<=size) { fileWriter<<b[i]<<‘-‘; i++; } fileWriter.close(); } void ActivitiesChoices::SF_time_read( ) { ifstream fileReader; fileReader.open("data.txt"); int i = 1 ; char c ; fileReader>>c ; //fileReader>>c ;// 2个字符 cout<<c ; while( i<=size ) { fileReader>>s[i]>>c ; cout<<s[i]<<‘ ‘ ; i++ ; } i = 1 ; //fileReader>>c ; // 3 个 字符 //cout<<c ; cout<<endl ; fileReader>>c ; cout<<c ; //fileReader>>c ; //cout<<c ; while( i <= size ) { fileReader>>f[i]>>c ; cout<<f[i]<<‘ ‘ ; i++ ; } cout<<endl ; fileReader.close() ; } // function: 递归 void ActivitiesChoices::PECURSIVE_ACTIVITY_SELECTOR( int i ,int n ) { int m = i + 1 ; while( m<=n && s[m]<f[i] ) m = m+1 ; if( m <= n ) { Result->push_front(m) ; this->PECURSIVE_ACTIVITY_SELECTOR(m,n) ; } } void ActivitiesChoices::Result_Show() { while(! Result->empty() ) { cout<<Result->back()<<endl ; Result->pop_back() ; } } // function: 非递归 void ActivitiesChoices::GREEDY_ACTIVITY_SELECTOR( ) { Result->clear(); Result->push_front(1); int i =1 ; int m ; for( m = 2 ; m <= size ; m++ ) { if( s[m]>=f[i] ) { Result->push_front(m) ; i = m ; } } } void ActivitiesChoices::Main( ) { this -> SF_time_set() ; this -> SF_time_read() ; this -> PECURSIVE_ACTIVITY_SELECTOR( 0 ,size ); this -> Result_Show(); cout<<endl; this -> GREEDY_ACTIVITY_SELECTOR(); this -> Result_Show(); } ActivitiesChoices::~ActivitiesChoices(void) { delete [] s,f ; } int main() { ActivitiesChoices * AC = new ActivitiesChoices(); AC ->Main(); delete AC; system("pause"); return 0 ; }
原文:http://blog.csdn.net/cqs_experiment/article/details/20281983
内容总结
以上是互联网集市为您收集整理的算法之路 直奔贪心全部内容,希望文章能够帮你解决算法之路 直奔贪心所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源:【匿名】