任务时间表
- 格式：docx
- 大小：2.36 MB
- 文档页数：18
MICROSOFT 任务时间表问题 [键入文档副标题]
[选取日期]
[在此处键入文档摘要。摘要通常为文档内容的简短概括。在此处键入文档摘要。摘要通常为文档内容的简短概括。] package任务时间表问题; publicclass Greedyjob { publicstaticint greedyJob(int []d,int []w,int []job) { int n=d.length-1; d[0]=0; job[0]=0; int k =1; job[1]=1; for(int i=2;i<=n;i++) { int r=k; while((d[job[r]])>d[i]&&(d[job[r]]!=r)) r--; if((d[job[r]]<=d[i])&&(d[i]>r)){ for(int m=k;m>r;m--) job[m+1]=job[m]; job[r+1]=i; k++; } } for(int i=1;i<=k;i++) w[job[i]]=0; int sum=0; for(int i=1;i<=n;i++) if(w[i]>0){ job[++k]=i; sum+=w[i]; } return sum; }
publicstaticint fasterJob(int d[],int w[],int []job,int s[]) //核心算法 //d[]为期限数组，w[]为延迟惩罚数组，job[]为所选及时任务数组，s[]为任务安排顺序 { int n=d.length-1; int []f=newint[n+1]; for(int i=0;i<=n;i++)f[i]=i; FastUnionFind U=new FastUnionFind(n); //创建并差集 int k=0,t=0; for(int i=1;i<=n;i++) { int m=(n可放置位置 if(f[m]>0)//任务可放入及时任务中 { k=k+1; job[k]=i; s[m]=i;//记录及时任务放置位置 if(f[m]>1){//同等价类的任务（同期限的任务）还有放置空间，合并等价类，确定下一等价类任务的放置位置 t=U.Find(f[m]-1); U.Union(t, m); } else t=0;//同等价类的任务（同期限的任务）已无放置空间，下一等价类任务将为非及时任务 f[m]=f[t]; } } for(int i=1;i<=k;i++)
w[job[i]]=0;//及时任务惩罚清零 int sum=0; for(int i=1;i<=n;i++) if(w[i]>0){ sum+=w[i]; for(int j=1;j<=n;j++) if(s[j]==0) {s[j]=i;break;} //将非及时任务加入安排队列中 } for(int i=1;i<=n;i++) System.out.print(s[i]); System.out.println(); return sum;//返回最小惩罚数 } }
publicclass FastUnionFind {//并差集
privateintparent[]; //父节点 intsize; //并差集大小
public FastUnionFind(int s) { size=s; parent=newint [size+1]; for(int i=0;i<=size;i++) parent[i]=-1; //用负数代表集合元素个数
} publicint Find(int x) //查找元素所在的等价类所在树的根节点 { int p=x; while(parent[p]>0) p=parent[p]; while(x!=p) { int temp=parent[x]; parent[x]=p; x=temp; } return x; }
publicvoid Union(int root1,int root2) //将量元素集合并到同一并差集下（同一树下） { int temp=parent[root1]+parent[root2]; //孩子结点个数 if(root2{ parent[root1]=root2; parent[root2]=temp; } else { parent[root2]=root1; parent[root1]=temp; } } }
publicclass Sort {//合并排序类
publicvoid mergeSort(work wo[]){ //对work数组按延期惩罚由大到小排列 int s=1; while(s{ mergePass(wo,s); s+=s; } }
publicvoid mergePass(work wo[],int s) { int i=1; while(i{ merge(wo,i,i+s-1,i+2*s-1); i=i+2*s; } if(i+smerge(wo,i,i+s-1,wo.length-1); }
publicvoid merge(work wo[],int l,int m,int r) {
int i=l; int j=m+1; while(i { if(wo[i].compareTo(wo[j])==-1) {
work k=wo[j]; for(int n=j-1;n>=i;n--) { wo[n+1]=wo[n]; } wo[i]=k;
} i++; } } } import javax.swing.*; import java.util.*;
publicclass InitialTree {//窗口中的年月树
publicstatic JTree Initial(){ String [][]y=new String[5][12]; for(int i=0;i<=4;i++) for(int j=0;j<=11;j++) y[i][j]=(2012+i)+"年"+(j+1)+"月";//子（月份）结点集 Hashtable hastable=newHashtable(); for(int i=0;i<=4;i++) hastable.put((2012+i)+"年",y[i]);//添加结点 JTree tree=new JTree(hastable); tree.setSize(300, 600);
return tree;
} }
publicclass work implementsComparable{//任物类
public String name; //任务名称 publicintwast; //延迟惩罚 publicintdeathline; //任务期限 public String month; //任务所属年月份
public work(String name, String month,int deathline,int wast) { this.name=name; this.month=month; this.deathline=deathline; this.wast=wast;
} publicint compareTo(Object x)//任务延迟惩罚比较 { int xt=((work)x).wast; if(wastif(wast==xt) return 0; elsereturn 1; }
} import javax.swing.*; import java.awt.*; import java.awt.event.*; import java.sql.*; import javax.swing.tree.*; import javax.swing.event.*; //创建简单窗口，动态显示任务时间表问题 publicclassTimeThingextends JFrame
implementsActionListener,TreeSelectionListener,Runnable { public JDesktopPane desktopPane=new JDesktopPane();//桌面 JInternalFrame jnew2=new JInternalFrame("完成顺序",true,true,true,true);//动态显示页面 private Statement stmt1; //用于数据库查询 private ResultSet rs1; work ww[];//任务数组
public TimeThing(work ww[],JDesktopPane desktopPane,JInternalFrame jnew2){ //此构造方法用于创建线程，经行任务动态选择 this.ww=ww; this.desktopPane=desktopPane; this.jnew2=jnew2; }
public TimeThing()//创建窗口 { super("任务时间表"); JMenuBar bar=new JMenuBar(); JPanel p1=new JPanel();p1.setMaximumSize(new Dimension(300,600)); JScrollPane scrollPane=new JScrollPane(); JTree tree=InitialTree.Initial();//生成年月树 tree.addTreeSelectionListener(this);//TreeSelectionEvent监听 scrollPane.setViewportView(tree); p1.setLayout(new BorderLayout()); p1.add(new JLabel("年中任务"),BorderLayout.NORTH); p1.add(scrollPane,BorderLayout.CENTER); bar.setOpaque(true); JMenu mfile=buildFileMenu();//创建菜单列表 bar.add(mfile); setJMenuBar(bar);
Container contentPane=getContentPane(); Box baseBox=Box.createHorizontalBox(); //水平Box布局 contentPane.add(baseBox); Box vBox=Box.createVerticalBox(); vBox.add(p1);//年月树
