活动选择问题代码（c++）

// //为什么会是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 ); } //二维是为了输出最大兼容活动集合