//
//为什么会是n+2维的呢?
#include <iostream>
#include <iomanip>
using namespace std;
const int activityNum = 11;
void activity_selection( const int starts[], const int finished[], int counts[][activityNum+2], int partition[][activityNum+2], const int actNum );
void print( const int partition[][activityNum+2], int i, int j );
int main()
{
int starts[] = { -1,1,3,0,5,3,5,6,8,8,2,12,INT_MAX };
int finished[] = { 0,4,5,6,7,8,9,10,11,12,13,14,INT_MAX };
int counts[activityNum+2][activityNum+2];
int partition[activityNum+2][activityNum+2];
activity_selection( starts, finished, counts, partition, activityNum );
cout << "最多有" << counts[0][activityNum+1] <<"个活动兼容"<< endl;
cout << "最大兼容活动集合为:";
print( partition, 0, activityNum+1 );
cout << endl;
#ifndef DEBUG
for( int i = 0; i < activityNum+2; ++i )
{
for( int j = 0; j < activityNum+2; ++j )
cout << setw(3) << counts[i][j];
cout<< endl;
}
cout << "partition"<<endl;
for( int i = 0; i < activityNum+2; ++i )
{
for( int j = 0; j < activityNum+2; ++j )
cout << setw(3) << partition[i][j];
cout<< endl;
}
#endif
}
void activity_selection( const int starts[], const int finished[], int counts[][activityNum+2],int partition[][activityNum+2], const int actNum )
{
int i,j,k;
for( i = 0; i < activityNum+2; ++i )
for( j = 0; j < activityNum+2; ++j )
{
counts[i][j] = 0;
partition[i][j] = 0;
}
for( i = activityNum; i >=0; --i )
{
for( j = i+1; j < activityNum+2; ++j )
{
for( k = i+1; k < j; ++k )
{
if( starts[k] >= finished[i] && finished[k] <= starts[j] )//s【i,j】不为空
{
if( counts[i][j] <= (counts[i][k] + 1 + counts[k][j]) )//如果有多个解,那么
//< 和 <=时输出的结果不同
{
counts[i][j] = (counts[i][k] + 1 + counts[k][j]);
partition[i][j] = k;
}
}
}
}
}//for
}
void print( const int partition[][activityNum+2], int i, int j )
{
if( partition[i][j] == 0 )
return;
cout <<setw(4) << partition[i][j];
print( partition, i, partition[i][j] );
print( partition, partition[i][j], j );
}
//二维是为了输出最大兼容活动集合
活动选择问题代码(c++)
5星 · 超过95%的资源 需积分: 50 21 浏览量
2011-09-22
10:57:59
上传
评论 1
收藏 2KB ZIP 举报
march_on
- 粉丝: 62
- 资源: 10
最新资源
- NetOps-py通过sftp替换网络设备启动文件
- STM32单片机FPGA毕设电路原理论文报告任务驱动教学法在单片机课程教学中的应用
- STM32单片机FPGA毕设电路原理论文报告任务驱动法在单片机教学中的应用
- STM32单片机FPGA毕设电路原理论文报告人造金刚石压机智能化压力测控系统设计
- 以某列为依据匹配多项(Excel版)
- STM32单片机FPGA毕设电路原理论文报告人体短臂离心机实验台的显示控制系统
- STM32单片机FPGA毕设电路原理论文报告人工气候室监控系统的环境控制器研究
- STM32单片机FPGA毕设电路原理论文报告染整自动线张力控制系统的设计
- 数据挖掘与机器学习-实验
- 基于Linux系统Nginx的动态网站的LNMP环境源码包
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈