帶期限的作業(yè)排序問題

1、帶期限的作業(yè)排序問題(1)答：c(x)的設(shè)計思路:當(dāng)x=1時，c(x)為所有作業(yè)的罰款金額總和,某節(jié)點m的估計值為c(x)，并對其進(jìn)行擴(kuò)展時，其有效的子節(jié)點a的c(x)為m的c(x)-a的罰款金額。對于u(x)初始時為作業(yè)罰款金額總和。之后，若隊列中的某一節(jié)點b的c(x)最小且小于u(x),則使u(x) =b. c(x)(2)(3)當(dāng)某節(jié)點的已經(jīng)被罰款項即c(x)U，則封殺此節(jié)點。(4)當(dāng)從根開始到當(dāng)前要加入的節(jié)點這條路徑中，共花費時間costtime ,最大截止期限為maxdeadtime，若maxdeadtimecosttime則此節(jié)點不可行，否則可行.(5)主要結(jié)構(gòu)及類型說明node q

2、ueue1000;/存放狀態(tài)空間樹中的節(jié)點Node結(jié)構(gòu)在構(gòu)造狀態(tài)空間樹時使用struct nodeint number;/所代表的作業(yè)在source的下標(biāo)int mayfine;/可能的罰款的金額即罰款金額的上限int currentfine;/到此節(jié)點止已罰款的金額bool iskilled;/是否被殺死 int timecost;/從根節(jié)點到此節(jié)點為止已花費的時間int parent;/父節(jié)點在queue的下標(biāo);Tast結(jié)構(gòu)在輸入作業(yè)信息時使用struct taskint number;/作業(yè)的序號int fine;/罰款金額int deadline;/截止期限int time;/完成此作

3、業(yè)所需的時間;int ans=0;/最小上界值在queue的下標(biāo)int minmayfine;/隊列中活結(jié)點的罰款上限的最小值即Uint activenumber=1;/活結(jié)點的數(shù)目const int N = ?;/N表示作業(yè)數(shù)int size = 1;/當(dāng)前隊列中的元素個數(shù)(6) 程序代碼思想：/使作業(yè)按截至期限的非降序排列，則對一個父節(jié)點s，要加入一個節(jié)點m，只要m的截至期限大于等于s.timecost+m所代表的作業(yè)的time#include#includeusing namespace std;struct nodeint number;/選擇的節(jié)點在source的下標(biāo)int mayf

4、ine;/可能的罰款的金額即罰款金額的上限int currentfine;/到此節(jié)點止已罰款的金額bool iskilled;/是否被殺死int timecost;/從根節(jié)點到此節(jié)點為止已花費的時間int parent;/父節(jié)點在queue的下標(biāo);struct taskint number;/作業(yè)的序號int fine;/罰款金額int deadline;/截止期限int time;/完成此作業(yè)所需的時間;/節(jié)點被殺死的條件是已罰款的金額超過了最小罰款金額 即currentfinemayfinenode queue1000;/存放狀態(tài)空間樹const int N = 4;/N表示作業(yè)數(shù)task

5、 sourceN+1 = 0,0,0,0, 1,5,1,1, 2,10,3,2, 3,6,2,1, 4,3,1,1;/作業(yè)集合int ans=0;/最小上界值在queue的下標(biāo)int minmayfine;/隊列中活結(jié)點的罰款上限的最小值int activenumber=1;/活結(jié)點的數(shù)目void init()/初始化隊列for (int i =1; i = N; i+)minmayfine +=sourcei.fine; queue0.mayfine = minmayfine;queue0.currentfine =0;queue0.iskilled =0;queue0.number = 0

6、;/作業(yè)的序號queue0.parent = -1;queue0.timecost =0;bool greater(task x,task y)if (x.deadline = y.deadline)return 1;elsereturn 0;/aloca為節(jié)點m在queue的下標(biāo),b為m的子節(jié)點x的作業(yè)在source的下標(biāo)，獲取x到目前為止已罰款數(shù)int getfine(int aloca,int b)int a = queuealoca.number;/a為節(jié)點m在source中的下標(biāo)int fine = queuealoca.currentfine;for(int i = a+1;i m

7、inmayfine )queueactive.iskilled = 1;active+;activenumber-;/活結(jié)點減少1continue;/向后選擇作業(yè)，直到所有的組合都選擇完a=queueactive.number+1;while (a=N)costtime = queueactive.timecost+sourcea.time;if (costtime = sourcea.deadline)queuesize.currentfine = getfine(active,a);/a為在source中的下標(biāo)queuesize.iskilled =0;queuesize.mayfine

8、= queueactive.mayfine - sourcea.fine;queuesize.parent = active;queuesize.number = a;queuesize.timecost = costtime;/尋找隊列中最終罰款的上限的最小值if(queuesize.mayfine minmayfine)minmayfine = queuesize.mayfine;/答案節(jié)點的上界即Uans = size;size+;/隊列長度增加activenumber+;/外層if結(jié)束a+;/內(nèi)層while結(jié)束/一個節(jié)點完全擴(kuò)展完了，就會被殺死，并且活結(jié)點數(shù)目減少1queueactive.iskilled =1;activenumber-;active+;/擴(kuò)展下