//
//为什么会是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 64 浏览量
2011-09-22
10:57:59
上传
评论 1
收藏 2KB ZIP 举报
march_on
- 粉丝: 62
- 资源: 10
最新资源
- 常用工具集参考用于图像等数据处理
- 音乐展示网页、基于Stenography的图像数字水印添加与提取,以及基于颜色矩和Tamura算法的图像相似度评估算法py源码
- 基于EmguCV(OpenCV .net封装),图像数字水印加解密算法的实现,其中包含最低有效位算法,离散傅里叶变换算法+文档书
- 基于matlab+DWT的图像水印项目,数字水印+源代码+文档说明+图片+报告pdf
- (优秀毕业设计)基于python实现的数字图像可视化水印系统的设计与实现,多种数字算法实现+源代码+文档说明+理论演示pdf
- 基于DWT-DCT-SVD和deflate压缩的数字水印方法python源码+Gui界面+演示视频(高分毕业设计)
- 基于matlab实现DWT、DCT、SVD算法数字图像水印可视化系统+GUI界面+文档说明+详细注释(高分毕业设计)
- NCIAE-Data-Structure大一大二笔记
- 学习wireshark笔记
- digital-image-数据可视化笔记
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈