问题描述和分析:《算法导论》p222——16.1活动选择问题.
这里给出了动态规划和贪心算法两种算法的代码:
view plaincopy to clipboardprint?
动态规划解法:
#include <iostream>
using namespace std;
const int N = 11;
int s[N+2];
int f[N+2];
int trace[N+2][N+2];//trace[i][j]跟踪子问题S(i,j)每次最优时的划分
int dp[N+2][N+2];//dp[i][j]表示子问题S(i,j)的最多兼容活动数
//S(i,j)={ak,fi<=sk<fk<=sj}表示在活动ai结束之后,在aj开始之前的活动集,则整个问题空间可表示为S(0,n+1),其中添加活动a0和an+1,s0=f0=0,sn+1=fn+1=2^32-1
//根据dp[i][j]的含义,假设S(i,j)中不包含任何的活动序列(即满足S(i,j)定义的活动不存在),则dp[i][j]=0;否则,假设ak时S(i,j)中存在的一个兼容活动,那
么这里存在问题S(i,j)的最优子结构:S(i,k)和S(k,j).
//根据上面叙述,可以定义问题的递归解结构:
//dp[i][j]=0,如果S(i,j) =NULL
//dp[i][j]=max{dp[i][k]+dp[k][j]+1},i<k<j
void dp_solve()
{
int i =0;
int j = 0;
int l = 0;
int k = 0;
for(i=1;i<=N+1;i++)
for(j=1;j<=N+1;j++)
if(i==j)
dp[i][j]=1;
dp[0][0] = dp[N+1][N+1] = 0;
for(l=1;l<N+2;l++)
for(i=0;i+l<N+2;i++)
{
j=i+l;
if(j<N+2)
{
dp[i][j] = 0;
trace[i][j] = 0;
for(k=i+1;k<j;k++)
{
if(f[i]<=s[k] && f[k]<=s[j])//寻找是dp[i][k]+dp[k][j]最大的值
{
if(dp[i][k] + dp[k][j]+1 > dp[i][j])
{
dp[i][j] = dp[i][k]+dp[k][j] +1;
trace[i][j] = k;
}
}
}
//cout << "dp["<<i<<"]["<<j<<"] = " << dp[i][j] << endl;
}
}
}
void print(int i,int j)
{
int k =0;
if(trace[i][j]==0)
return;
k = trace[i][j];
cout << k << " ";
print(i,k);
print(k,j);
}
int main()
{
int i =0;
for(i=1;i<N+1;i++)
cin>> s[i];
for(i=1;i<N+1;i++)
cin>> f[i];
s[0]=-1;
f[0] = 0;
s[N+1]=65535;
f[N+1] = 65536;
dp_solve();
print(0,N+1);
cout << endl;
}
动态规划解法:
#include <iostream>
using namespace std;
const int N = 11;
int s[N+2];
int f[N+2];
int trace[N+2][N+2];//trace[i][j]跟踪子问题S(i,j)每次最优时的划分
int dp[N+2][N+2];//dp[i][j]表示子问题S(i,j)的最多兼容活动数
//S(i,j)={ak,fi<=sk<fk<=sj}表示在活动ai结束之后,在aj开始之前的活动集,则整个问题空间可表示为S(0,n+1),其中添加活动a0和an+1,s0=f0=0,sn+1=fn+1=2^32-1
//根据dp[i][j]的含义,假设S(i,j)中不包含任何的活动序列(即满足S(i,j)定义的活动不存在),则dp[i][j]=0;否则,假设ak时S(i,j)中存在的一个兼容活动,那
么这里存在问题S(i,j)的最优子结构:S(i,k)和S(k,j).
//根据上面叙述,可以定义问题的递归解结构:
//dp[i][j]=0,如果S(i,j) =NULL
//dp[i][j]=max{dp[i][k]+dp[k][j]+1},i<k<j
void dp_solve()
{
int i =0;
int j = 0;
int l = 0;
int k = 0;
for(i=1;i<=N+1;i++)
for(j=1;j<=N+1;j++)
if(i==j)
dp[i][j]=1;
dp[0][0] = dp[N+1][N+1] = 0;
for(l=1;l<N+2;l++)
for(i=0;i+l<N+2;i++)
{
j=i+l;
if(j<N+2)
{
dp[i][j] = 0;
trace[i][j] = 0;
for(k=i+1;k<j;k++)
{
if(f[i]<=s[k] && f[k]<=s[j])//寻找是dp[i][k]+dp[k][j]最大的值
{
if(dp[i][k] + dp[k][j]+1 > dp[i][j])
{
dp[i][j] = dp[i][k]+dp[k][j] +1;
trace[i][j] = k;
}
}
}
//cout << "dp["<<i<<"]["<<j<<"] = " << dp[i][j] << endl;
}
}
}
void print(int i,int j)
{
int k =0;
if(trace[i][j]==0)
return;
k = trace[i][j];
cout << k << " ";
print(i,k);
print(k,j);
}
int main()
{
int i =0;
for(i=1;i<N+1;i++)
cin>> s[i];
for(i=1;i<N+1;i++)
cin>> f[i];
s[0]=-1;
f[0] = 0;
s[N+1]=65535;
f[N+1] = 65536;
dp_solve();
print(0,N+1);
cout << endl;
}
view plaincopy to clipboardprint?
贪心算法解法:
#include <iostream>
using namespace std;
const int N = 11;
int s[N];
int f[N];
void greet_activity()
{
int i =0;
int m = 0;
int fm = f[m];
cout << m+1 << " ";
i= m+1;
while(i<N)
{
if(s[i]>=fm )
{
m=i;
cout << i+1 << " " ;//数组从0开始,编号为数组下标+1
fm = f[m];
i++;
}
else
{
i++;
}
}
}
int main()
{
int i =0;
for(i=0;i<N;i++)
cin>> s[i];
for(i=0;i<N;i++)
cin>> f[i];//结束时间按有序输入
greet_activity();
cout << endl;
}
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/clearriver/archive/2009/08/17/4457143.aspx
分享到:
相关推荐
0023算法笔记——【贪心算法】哈夫曼编码问题--16页.pdf
算法这么课程的结课论文,以最短路径算法为例描述贪心算法
贪心算法中,背包问题的源代码。可以编译运行,用快速排序实现的。
贪心算法——用最少硬币找出n分钱的问题,以及代码。终于解决了
马踏棋盘问题(骑士巡游问题)的基于贪心算法优化深度搜索可视化实现 用c语言实现的,在命令台中会动态的显示棋盘上棋子路径
机器学习实习生面试常考的算法——贪心算法, python代码实现,案例+PPT讲解
算法这门课程的结课论文,以最短路径算法为例描述贪心算法
NOIP基础算法——贪心和分治.ppt
NOIP基础算法——贪心和分治pasal.ppt
下的几个都不好,还不如自己传个好点的。 算法设计基础之贪心算法
基础算法——贪心和分治PPT学习教案.pptx
NOIP基础算法——贪心和分治_图文.ppt.ppt
第四章——贪心算法 1.背包问题 2.多机调度问题 3.单源最短路径-Dijkstra算法 4.最小代价生成树问题-Prim算法 5.最小代价生成树问题-Kruskal算法 第五章——动态规划算法 1.最优二叉搜索树 2.每对节点最短距离 3....
在18位整数...16485679数中删除4个数字的贪心操作步骤。 1 6 4 8 5 6 7 9 出现1删除6 6 4 8 5 6 7 9 出现4删除4 6 8 5 6 7 9 出现6删除6 8 5 6 7 9 出现5删除5 8 6 7 9 删除4个数字后,最大的数是8679
贪心算法。经典算法. OIER必备。 找的很辛苦。请关注
背包问题(Knapsack ...试用贪心算法和动态规划方法来解决0-1背包问题,采用所提供的数据集合. 作业需要提供实验报告,包括伪代码和运行代码,以及每个测试问题的运行时间、结果,如果无法在有限时间得到答案则为N.A.
最小生成树——贪心算法
取得最优解一直是解决背包问题的最终目的,就贪心算法的动态规划关系以及方案在解决背包问题上作比较,但贪心法在什么时候都能取到最优解并无一般结论,而对于普通背包问题我们却有一个完美的结果——贪心法可取到最优...
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的