哎呀，大家好。憋了我久了，终于回校了，回校以后真不想说我的大学了，你说我回来这么早来准备面试，你给供暖不行呀，暖气冰凉冰凉的，你想冻死学生呀，学生回来早点好找工作，找个世界500强也不是给你争脸麽。如果不是好好学习的同学，他会回校这么早么？你咋不知道好歹呢？还不如上班呢，呜呜呜。回到正题，代码一年前写的，自己感觉真烂，各种不满意，注释，异常，优化，可读性，最近在整理复习，就朝花夕拾了。
动态规划例题麽，当然用动态规划解题了，规模从小到大，逐渐建表啦。这个很简单，但是我们要掌握的不是这个，而是动态规划的条件
- 最有子结构性质
- 无后向性：换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
- 重叠子问题
为了测试算法，随机生成的数据做实验，数据如下
程序结果截图
dp_车间调度.h
#include <fstream> #include <iostream> using namespace std; int const size = 100 ; // 车间装在线 class thread { public: // var start time int e ; // var end time int x ; // var 车间移动时间 int * t ; // var 车间装配时间 int * a ; // 路线方案时间 int * f ; // 路线方案 int * line ; // 车间长度 int length ; //function : 构造函数 thread( int l ) ; // function: 装配时间 void A_Prepare( int * data ) ; // function: 移动时间 void T_prepare( int * data ) ; // function: 析构函数 ~thread( void ) ; }; //function : 构造函数 thread::thread( int l ) { t = new int [ l ] ; a = new int [ l ] ; f = new int [ l ] ; line = new int [ l ] ; this -> length = l ; }; // function: 装配时间 void thread::A_Prepare( int * data ) { int i = 0 ; e = data[0]; while( i < this -> length ) { a[i] = data[i+1] ; i++ ; } }; // function: 移动时间 void thread::T_prepare( int * data ) { int i = 0 ; while( i < this -> length - 1 ) { t[i] = data[i] ; i++ ; } x = data[i] ; }; // function: 析构函数 thread::~thread(void) { delete [] t ; delete [] a ; delete [] line ; delete [] f ; }; // dp_车间调度问题对象 class JobShopSchedulingProblem { // var: data int * Aint1; int * Aint2; int * Aint3; int * Aint4; // var:two thread thread * T1 ; thread * T2 ; //var:result time and way int f; int l; public: // function:构造函数 JobShopSchedulingProblem( ); // function:数据准备 void dataPrepare( ); // function:获取数据 void dataRead( ); // function:dp computer the way void FASTEST_way( int n ) ; // function:打印路线 void PrintStations( int n ) ; // function:主函数 void Main(int n); // function:show data void Showdata(int n); // function:析构函数 ~JobShopSchedulingProblem( void ); }; // function:构造函数 JobShopSchedulingProblem::JobShopSchedulingProblem() { Aint1 = new int[size]; Aint2 = new int[size]; Aint3 = new int[size]; Aint4 = new int[size]; } // function:数据准备 void JobShopSchedulingProblem::dataPrepare() { ofstream fileWriter; fileWriter.open("thread_1_t.txt"); fileWriter.clear(); int i , j = 0 ; while( j < size ) { i= rand()%100; fileWriter<<i<<‘/‘; j++; } fileWriter.close(); fileWriter.open("thread_1_a.txt"); fileWriter.clear(); j = 0 ; while( j < size ) { i= rand()%100; fileWriter<<i<<‘/‘; j++; } fileWriter.close(); fileWriter.open("thread_2_t.txt"); fileWriter.clear(); j = 0 ; while( j < size ) { i= rand()%100; fileWriter<<i<<‘/‘; j++; } fileWriter.close(); fileWriter.open("thread_2_a.txt"); fileWriter.clear(); j = 0 ; while( j < size ) { i= rand()%100; fileWriter<<i<<‘/‘; j++; } fileWriter.close(); } // function:获取数据 void JobShopSchedulingProblem::dataRead() { ifstream fileReader ; fileReader.open("thread_1_a.txt") ; int i = 0 ; char c ; while(i<size) { fileReader>>Aint1[i]>>c; //cout<<Aint1[i]<<endl; i++; } fileReader.close() ; fileReader.open("thread_1_t.txt") ; i = 0 ; while(i<size) { fileReader>>Aint2[i]>>c; //cout<<Aint1[i]<<endl; i++; } fileReader.close() ; fileReader.open("thread_2_a.txt") ; i = 0 ; while(i<size) { fileReader>>Aint3[i]>>c; //cout<<Aint1[i]<<endl; i++; } fileReader.close() ; fileReader.open("thread_2_t.txt") ; i = 0 ; while( i < size ) { fileReader>>Aint4[i]>>c ; //cout<<Aint1[i]<<endl ; i++ ; } fileReader.close() ; } // function:dp computer the way void JobShopSchedulingProblem::FASTEST_way( int n ) { T1 = new thread( n ) ; T2 = new thread( n ) ; T1->A_Prepare( Aint1 ) ; T1->T_prepare( Aint2 ) ; T2->A_Prepare( Aint3 ) ; T2->T_prepare( Aint4 ) ; (T1->line)[0] = 0; (T2->line)[0] = 0; (T1->f)[0] = T1->e +(T1->a)[0]; (T2->f)[0] = T2->e +(T2->a)[0]; int j = 0 ; for( j =1 ;j<n;j++) { if( (T1->f)[j-1]+(T1->a)[j] <= (T2->f)[j-1] + (T2->t)[j-1]+(T1->a)[j] ) { (T1->f)[j] = (T1->f)[j-1]+(T1->a)[j] ; (T1->line)[j] = 1 ; } else { (T1->f)[j] = (T2->f)[j-1] + (T2->t)[j-1]+(T1->a)[j] ; (T1->line)[j] = 2 ; } if( (T2->f)[j-1]+(T2->a)[j] <= (T1->f)[j-1] + (T1->t)[j-1]+(T2->a)[j] ) { (T2->f)[j] = (T2->f)[j-1]+(T2->a)[j] ; (T2->line)[j] = 2 ; } else { (T2->f)[j] = (T1->f)[j-1] + (T1->t)[j-1]+(T2->a)[j] ; (T2->line)[j] = 1 ; } } if((T1->f)[n-1]+T1->x <= (T2->f)[n-1] + T2->x ) { f = (T1->f)[n-1]+T1->x; l = 1; } else { f = (T2->f)[n-1] + T2->x ; l = 2 ; } } // function:打印路线 void JobShopSchedulingProblem::PrintStations( int n ) { int i = l ; int data = f ;; cout<<"line:\t"<<i<<" station:\t"<<n<<"\t "<<data<<" \t "<<endl; for( int j = n-1 ; j >= 0 ; j-- ) { if( i == 1 ) { i = (T1->line)[j]; //data = (T1->f)[j]; } else { i = (T2->line)[j]; //data = (T2->f)[j]; } cout<<"line:\t"<<i<<" station:\t"<<j<<"\t f1,"<<j<<"\t"<<(T1->f)[j]<<" \t f2,"<<j<<" \t "<<(T2->f)[j]<<endl; } } // function:主函数 void JobShopSchedulingProblem::Main(int n) { this->dataPrepare(); this->dataRead(); this->FASTEST_way(n); this->Showdata(n); this->PrintStations(n); } // function:show data void JobShopSchedulingProblem::Showdata(int n) { if(n <= 0) exit(0); cout<<"data follows"<<endl; cout<<"T1->e= "<<T1->e<<" ,T2->e= "<<T2->e<<endl; for(int i = 0; i<n-1; i++) { cout<<i<<" , T1->a= "<<(T1->a)[i]<<" , T1->t= "<<(T1->t)[i]<<" ,T2->a= "<<(T2->a)[i]<<" ,T2->t= "<<(T2->t)[i]<<endl; } cout<<n-1<<" , T1->a= "<<(T1->a)[n-1]<<" ,T2->a= "<<(T2->a)[n-1]<<endl; cout<<"T1->x= "<<T1->x<<" ,T2->x= "<<T2->x<<endl; cout<<"data show over"<<endl; } // function:析构函数 JobShopSchedulingProblem::~JobShopSchedulingProblem(void) { delete [] Aint1 ; delete [] Aint2 ; delete [] Aint3 ; delete [] Aint4 ; }
test.cpp#include "dp_车间调度.h" int main( ) { JobShopSchedulingProblem * DP = new JobShopSchedulingProblem(); DP->Main(15); delete DP; system("pause"); return 0 ; }
原文：http://blog.csdn.net/cqs_experiment/article/details/19212557
