带期限的作业排序问题

带期限的作业排序问题(1)答：c`(x)的设计思路:当x=1时，c`(x)为所有作业的罚款金额总和,某节点m的估计值为c`(x)，并对其进行扩展时，其有效的子节点a的c`(x)为m的c`(x)-a的罚款金额。对于u(x)初始时为作业罚款金额总和。之后，若队列中的某一节点b的c`(x)最小且小于u(x),则使u(x)=b.c`(x)(2)(3)当某节点的已经被罚款项即c(x)U，则封杀此节点。(4)当从根开始到当前要加入的节点这条路径中，共花费时间costtime,最大截止期限为maxdeadtime，若maxdeadtimecosttime则此节点不可行，否则可行.(5)主要结构及类型说明nodequeue[1000];//存放状态空间树中的节点Node结构在构造状态空间树时使用structnode{intnumber;//所代表的作业在source[]的下标intmayfine;//可能的罚款的金额即罚款金额的上限intcurrentfine;//到此节点止已罚款的金额booliskilled;//是否被杀死inttimecost;//从根节点到此节点为止已花费的时间intparent;//父节点在queue[]的下标};Tast结构在输入作业信息时使用structtask{intnumber;//作业的序号intfine;//罚款金额intdeadline;//截止期限inttime;//完成此作业所需的时间};intans=0;//最小上界值在queue的下标intminmayfine;//队列中活结点的罚款上限的最小值即Uintactivenumber=1;//活结点的数目constintN=?;//N表示作业数intsize=1;//当前队列中的元素个数(6)程序代码思想：//使作业按截至期限的非降序排列，则对一个父节点s，要加入一个节点m，只要m的截至期限大于等于s.timecost+m所代表的作业的time#includeiostream#includealgorithmusingnamespacestd;structnode{intnumber;//选择的节点在source[]的下标intmayfine;//可能的罚款的金额即罚款金额的上限intcurrentfine;//到此节点止已罚款的金额booliskilled;//是否被杀死inttimecost;//从根节点到此节点为止已花费的时间intparent;//父节点在queue[]的下标};structtask{intnumber;//作业的序号intfine;//罚款金额intdeadline;//截止期限inttime;//完成此作业所需的时间};//节点被杀死的条件是已罚款的金额超过了最小罚款金额即currentfinemayfinenodequeue[1000];//存放状态空间树constintN=4;//N表示作业数tasksource[N+1]={{0,0,0,0},{1,5,1,1},{2,10,3,2},{3,6,2,1},{4,3,1,1}};//作业集合intans=0;//最小上界值在queue的下标intminmayfine;//队列中活结点的罚款上限的最小值intactivenumber=1;//活结点的数目voidinit()//初始化队列{for(inti=1;i=N;i++){minmayfine+=source[i].fine;}queue[0].mayfine=minmayfine;queue[0].currentfine=0;queue[0].iskilled=0;queue[0].number=0;//作业的序号queue[0].parent=-1;queue[0].timecost=0;}boolgreater(taskx,tasky){if(x.deadline=y.deadline)return1;elsereturn0;}//aloca为节点m在queue[]的下标,b为m的子节点x的作业在source[]的下标，获取x到目前为止已罚款数intgetfine(intaloca,intb){inta=queue[aloca].number;//a为节点m在source[]中的下标intfine=queue[aloca].currentfine;for(inti=a+1;ib;i++)fine+=source[i].fine;returnfine;}voidconstruction(){sort(source+1,source+N+1,greater);//截止期限按非降序排列intsize=1;//当前队列中的元素个数intactive=0;//正在扩展的活结点的下标inta;intcosttime;while(activenumber!=0){//当一个节点已罚的款数大于最终罚款的上界的最小值，则杀死并查找下一个活结点if(queue[active].currentfineminmayfine){queue[active].iskilled=1;active++;activenumber--;//活结点减少1continue;}//向后选择作业，直到所有的组合都选择完a=queue[active].number+1;while(a=N){costtime=queue[active].timecost+source[a].time;if(costtime=source[a].deadline){queue[size].currentfine=getfine(active,a);//a为在source[]中的下标queue[size].iskilled=0;queue[size].mayfine=queue[active].mayfine-source[a].fine;queue[size].parent=active;queue[size].number=a;queue[size].timecost=costtime;//寻找队列中最终罚款的上限的最小值if(queue[size].mayfineminmayfine){minmayfine=queue[size].mayfine;//答案节点的上界即Uans=size;}size++;//队列长度增加activenumber++;}//外层if结束a++;}//内层while结束//一个节点完全扩展完了，就会被杀死，并且活结点数目减少1queue[active].iskilled=1;activenumber--;active++;//扩展下一个节点}//外层while结束while(ans!=0){coutsource[queue[ans].number].number;ans=queue[ans].parent;}coutendl;}voidmain(){init();construction();}