独立任务最优调度问题+算法设计

问题描述：独立任务最优调度，又称双机调度问题：用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。研究一个实例：n=6, a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 11, 3, 4}。

#include 
#include
#include  
using namespace std;  
const int SIZE=50;  
const int MAXINT=999;  
int main（）{  
      
while（1）{  
int Na[SIZE]b[SIZE]SumA[SIZE]SumB[SIZE];  
int tempSumAtempSumBMinSum;  
int i=0jk;  
tempSumA=tempSumB=0;
int data;
int oriData[SIZE]; 
//记录A，B完成当前任务所需时间  
//Read input.txt
	ifstream ifile;
    ifile.open（“input.txt“）;  
	if（ifile.eof（）） 
    {
        cerr<<“Fail to open the file input.txt“<        return 1;
    }
while（ifile>>data）
    {
		oriData[i++]=data;    //Recording data
    }

	N=（int）oriData[0];    //the number of task
//	i=0;
	for （i=1;i<=N;i++）
	{
		a[i]=oriData[i];
		tempSumA+=a[i];  
		SumA[i]=tempSumA;
	}
	for （i=1j=N+1;j<=2*N;j++i++）
	{
		b[i]=oriData[j];
		tempSumB+=b[i];  
		SumB[i]=tempSumB;
	}

	//Show data of input.txt and data will process.
	cout<<“Input.txt Data:“<	cout<	for （i=1;i<=2*N; ）
	{
		cout<		i++;
		cout<		i++;		
	}
/*	cout<<“Data will process:“<	for （i=0;i	{
		cout<	}*/
	cout<    ifile.close（）;
/*cin>>N;  
if（N<=0）break;  
int tempSumAtempSumBMinSum;  
int ijk;  
tempSumA=tempSumB=0;  
for（i=1;i<=N;i++）{  
cin>>a[i];  
tempSumA+=a[i];  
SumA[i]=tempSumA;  
}  
for（i=1;i<=N;i++）{  
cin>>b[i];  
tempSumB+=b[i];  
SumB[i]=tempSumB;  
}  */
MinSum=（tempSumB>tempSumA）?tempSumA:tempSumB;  
//时间上限AB总和的最小值  
///动态二维数组   
int *MaxTime=new int [MinSum+1];  
int **F=new int*[N+1];  
for（i=0;iF[i]=new int [MinSum+1];  
SumB[0]=0;  
for（i=0;i<=N;i++）{  
F[i][0]=SumB[i];//SumB[0]没赋值，调试时会输出地址   
for（j=1;j<=MinSum;j++）  
F[i][j]=0;  
}  
/*for（i=0;i<=N;i++）{ 
for（j=0;j<=MinSum;j++） 
cout<cout<} 
cout<int temp;  
for（k=1;k<=N;k++）{  
   temp=（SumA[k]>SumB[k]）?SumB[k]:SumA[k];  
   for（i=1;i<=temp;i++）{ //A最多用AB前k任务的最小值，如果B最少就全用B做。  
      if（i>=a[k]）//等于号不能少   
		  F[k][i]=（F[k-1][i]+b[k]      else F[k][i]=F[k-1][i]+b[k];  
                        }   
                  }  
                    
/*for（i=0;i<=N;i++）{ 
for（j=0;j<=MinSum;j++） 
cout<cout<                  } 
cout<        
temp=MAXINT;  
for（i=0;i<=MinSum;i++）{  
	MaxTime[i]=（i>F[N][i]）?i:F[N][i];  
if（temp>MaxTime[i]）  
temp=MaxTime[i];  
                       }  
//cout<
//out.txt
ofstream ofile;  //write file
	ofile.open（“output.txt“）;
/*	int result=0;
	for（int i=0;i	{
		result+=abs（Data[i]-m）;
	}*/
	ofile<ofile.close（）;
cout<<“最优时间为：“<return 0;
//while（1）;
///////////////////////////////////  
/*for（i=0;idelete [] F[i];  
delete [] F;  
delete [] MaxTime;  
F=NULL;   */
}  
////////////////////////////////  
//system（“pause“）;  
//re

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2011-05-16 13:32  task\
     目录           0  2011-05-16 13:32  task\Debug\
     文件      358378  2011-05-13 09:36  task\Debug\Pipe_select.obj
     文件      569393  2011-05-14 00:12  task\Debug\task.exe
     文件      819304  2011-05-14 00:12  task\Debug\task.ilk
     文件      355378  2011-05-14 00:12  task\Debug\task.obj
     文件     2116212  2011-05-13 10:04  task\Debug\task.pch
     文件     1156096  2011-05-14 00:12  task\Debug\task.pdb
     文件       82944  2011-05-14 00:12  task\Debug\vc60.idb
     文件      118784  2011-05-14 00:12  task\Debug\vc60.pdb
     文件          29  2011-05-13 10:12  task\input.txt
     文件           4  2011-05-14 00:12  task\output.txt
     文件        3097  2011-05-14 00:06  task\task.cpp
     文件        3377  2011-05-14 00:12  task\task.dsp
     文件         531  2011-05-14 00:15  task\task.dsw
     文件       41984  2011-05-14 00:15  task\task.ncb
     文件       48640  2011-05-14 00:15  task\task.opt
     文件        1105  2011-05-14 00:12  task\task.plg