神马文学网0-1问题
来源：百度文库 编辑：神马文学网 时间：2024/05/01 07:36:36
问题描述和分析：《算法导论》p222——16.1活动选择问题.这里给出了动态规划和贪心算法两种算法的代码：view plaincopy to clipboardprint?
动态规划解法：
#include
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//根据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},ivoid 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 for(i=0;i+l {
j=i+l;
if(j {
dp[i][j] = 0;
trace[i][j] = 0;
for(k=i+1;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["< }
}
}
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 cin>> s[i];
for(i=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
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//根据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},ivoid 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 for(i=0;i+l {
j=i+l;
if(j {
dp[i][j] = 0;
trace[i][j] = 0;
for(k=i+1;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["< }
}
}
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 cin>> s[i];
for(i=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
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 {
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 cin>> s[i];
for(i=0;i cin>> f[i];//结束时间按有序输入
greet_activity();
cout << endl;
}
贪心算法解法：
#include
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 {
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 cin>> s[i];
for(i=0;i cin>> f[i];//结束时间按有序输入
greet_activity();
cout << endl;
}
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/08/17/4457143.aspx
动态规划解法：
#include
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
么这里存在问题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
{
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
j=i+l;
if(j
dp[i][j] = 0;
trace[i][j] = 0;
for(k=i+1;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["<
}
}
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
for(i=1;i
s[0]=-1;
f[0] = 0;
s[N+1]=65535;
f[N+1] = 65536;
dp_solve();
print(0,N+1);
cout << endl;
}
动态规划解法：
#include
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
么这里存在问题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
{
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
j=i+l;
if(j
dp[i][j] = 0;
trace[i][j] = 0;
for(k=i+1;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["<
}
}
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
for(i=1;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
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
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
for(i=0;i
greet_activity();
cout << endl;
}
贪心算法解法：
#include
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
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
for(i=0;i
greet_activity();
cout << endl;
}
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/08/17/4457143.aspx