資源簡介
問題描述:獨立任務最優調度,又稱雙機調度問題:用兩臺處理機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;i F[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;i delete?[]?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
- 上一篇:攻擊軟件.zip
- 下一篇:Swf格式圖片提取工具
評論
共有 條評論