动态规划——贪心算法——活动选择问题 收藏

问题描述和分析：《算法导论》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