问题描述和分析:《算法导论》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; } 贪心算法解法: #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 |
|