問題描述

? ? ? ? 一個(gè)單位時(shí)間任務(wù)是恰好需要一個(gè)單位時(shí)間完成的任務(wù)。給定一個(gè)單位時(shí)間任務(wù)的有限集S.關(guān)于S的一個(gè)時(shí)間表用于描述S中單位時(shí)間任務(wù)的執(zhí)行次序。

? ? ? ? 如：給定單位時(shí)間任務(wù)集S各任務(wù)截止時(shí)間和誤時(shí)懲罰，截止時(shí)間d[i]{4,2,4,3,1,4,6}，誤時(shí)懲罰w[i]{70,60,50,40,30,20,10},求解最優(yōu)時(shí)間表，計(jì)算最小總誤時(shí)懲罰。
?

思路分析過程

? ? ? ? 問題要使所有任務(wù)的總誤時(shí)懲罰最小，容易想到采用貪心策略：誤時(shí)懲罰大的任務(wù)先執(zhí)行。這樣，即使有任務(wù)不能按時(shí)執(zhí)行，懲罰值也是剩下較小的。

? ? ? ? 但是，直接將誤時(shí)懲罰大的任務(wù)從前往后排是否是最好的貪心策略呢？答案是否定的。因?yàn)槊總€(gè)任務(wù)都有一個(gè)時(shí)間底線，在時(shí)間底線之前執(zhí)行都不會(huì)受到懲罰。假設(shè)有這樣一種情況：有兩項(xiàng)任務(wù)，序號(hào)是1、2，誤時(shí)懲罰分別為70、60，時(shí)間底線分別為2、1。如果按照上面的貪心策略，執(zhí)行次序?yàn)?、2，任務(wù)2因?yàn)槌^時(shí)間底線而被懲罰。而事實(shí)上，最優(yōu)的貪心策略是執(zhí)行次序?yàn)?、1，兩個(gè)任務(wù)都不會(huì)收到懲罰。?

? ? ? ? 綜合考慮誤時(shí)懲罰和時(shí)間底線兩個(gè)因素，我們的算法需要使每個(gè)任務(wù)在不誤時(shí)的前提下，盡可能向后安排，留給其他任務(wù)最大的執(zhí)行空間。按照這種思想得到改進(jìn)的貪心策略：誤時(shí)懲罰大的任務(wù)優(yōu)先排到它的時(shí)間底線，如果該時(shí)間已經(jīng)有任務(wù)，則向前安排；如果前面都已經(jīng)有任務(wù)（懲罰在所難免），則從最后向前安排。?

?

詳細(xì)設(shè)計(jì)說明書

變量：in Scanner類型的變量便于控制臺(tái)接收數(shù)據(jù)

方法：

main(String[]):void主方法，入口方法。
show(int[],int[],int[],int[]):void參數(shù)列表分別為截至?xí)r間，誤時(shí)懲罰，時(shí)間表，原始數(shù)據(jù)下表。展示菜單列表。
greedyJob(int[],int[],int[]):void參數(shù)列表分別為截至?xí)r間，誤時(shí)懲罰，時(shí)間表。計(jì)算最優(yōu)時(shí)間表。
superSort(int[],int[],int[]):void參數(shù)列表分別為截至?xí)r間，誤時(shí)懲罰，時(shí)間表。排序。

源代碼

import java.util.Scanner; /*** @time 2016-06-11* @Description 計(jì)算任務(wù)時(shí)間表問題*/ public class TimeTable {//聲明靜態(tài)的掃描器類便于調(diào)用static Scanner in = new Scanner(System.in);/*** 主方法* @param args*/public static void main(String args[]) {/*** 測試用例 * int[] v1 = { 0, 4, 2, 4, 3, 1, 4, 6 }; * int[] w1 = { 0, 70, 60,50, 40, 30, 20, 10 };*/System.out.println("請(qǐng)輸入任務(wù)集的大小：");int size = in.nextInt();int[] v1 = new int[size + 1];int[] w1 = new int[size + 1]; int[] indexs=new int[v1.length];int time = 0;int passtime = 0; for (int i = 0; i < indexs.length; i++) {indexs[i]=i;}System.out.println("請(qǐng)分別輸入各任務(wù)截至?xí)r間：");for (int i = 1; i <= size; i++) {System.out.print("第" + i + "個(gè)任務(wù)的截至?xí)r間：");time = in.nextInt();v1[i] = time;}System.out.println("請(qǐng)分別輸入各任務(wù)誤時(shí)懲罰：");for (int i = 1; i <= size; i++) {System.out.print("第" + i + "個(gè)任務(wù)的誤時(shí)懲罰：");passtime = in.nextInt();w1[i] = passtime;}int[] u1 = new int[v1.length];new TimeTable().show(v1, w1, u1,indexs);}/*** 顯示方法show* @param v1 截止時(shí)間* @param w1 誤時(shí)懲罰* @param u1 最優(yōu)時(shí)間表*/public void show(int[] v1, int[] w1, int[] u1,int[] indexs) {SuperSort(v1, w1,indexs);int total=greedyjob(v1, w1, u1);System.out.println("<<時(shí)間表問題>>");while (true) {System.out.println("\n1.總誤時(shí)懲罰為");System.out.println("2.最優(yōu)時(shí)間表為");System.out.println("0.退出\n");System.out.println("---------------------------------");System.out.print("請(qǐng)選擇>");int choose = in.nextInt();switch (choose) {case 1:System.out.println("總誤時(shí)懲罰為：" +total);System.out.println("-----------------------------");break;case 2:System.out.print("最優(yōu)時(shí)間表為：");for (int i = 1; i <= v1.length - 1; i++) {System.out.print(indexs[u1[i]] + " ");} System.out.println();System.out.println("-----------------------------"); break;case 0:System.err.println("退出成功！");System.out.println("-----------------------------"); System.exit(0);}}}/*** 主要計(jì)算方法* @param d 截止時(shí)間* @param w 誤時(shí)懲罰* @param job 最優(yōu)時(shí)間表* @return 總誤時(shí)懲罰*/public int greedyjob(int[] d, int[] w, int[] job) {int n = d.length - 1;d[0] = 0;job[0] = 0;int k = 1;job[1] = 1;int sum = 0;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;}for (int i = 1; i <= n; i++) {if (w[i] > 0) {job[++k] = i;sum += w[i];}}return sum;} /*** 排序：對(duì)相同截止時(shí)間的誤時(shí)懲罰進(jìn)行降序排列；* @param d 截止時(shí)間* @param w 誤時(shí)懲罰*/public void superSort(int[] d, int[] w, int[] indexs) {for (int i = 1; i < d.length - 1; i++) {for (int j = i + 1; j < d.length; j++) {if (w[i] < w[j]) {int temp = w[i];w[i] = w[j];w[j] = temp;temp = indexs[i];indexs[i] = indexs[j];indexs[j] = temp;temp = d[i];d[i] = d[j];d[j] = temp;}}}} } }

遇到問題

? ? ? ? 算是很快完成算法的要求，測試也是發(fā)現(xiàn)了一些問題，于是嘗試修改代碼，改進(jìn)代碼，過程中我們用過新的算法，180度的代碼大轉(zhuǎn)換，最終還是無法解決問題，于是只有一行一行檢查代碼，查bug，當(dāng)看到一個(gè)交換數(shù)字的算法代碼塊時(shí)，我真的是既慚愧又很無奈呀，僅僅是兩個(gè)數(shù)組小標(biāo)寫反了，導(dǎo)致我們無用工作了兩天，在做課程設(shè)計(jì)初期，算法部分變量不清楚具體含義，經(jīng)過調(diào)試測試，最終明白，排序方法構(gòu)建時(shí)，大意出錯(cuò)，導(dǎo)致長時(shí)間代碼無法通過測試。

?

總結(jié)

? ? ? ? 通過實(shí)際操作實(shí)驗(yàn)加深了對(duì)時(shí)間表問題的理解，同時(shí)也學(xué)到了相關(guān)的很多知識(shí)，貪心算法和任務(wù)調(diào)度問題的理解也深入了解了不少，整個(gè)過程中，我深刻的體會(huì)到了編寫程序是必須加倍小心，盡量或不出現(xiàn)嘗試性問題，否則會(huì)發(fā)生很多意想不到的事，代碼編寫細(xì)心很重要，總之算法重在在理解，代碼實(shí)現(xiàn)只是一種表現(xiàn)形式，確是很好的表現(xiàn)。團(tuán)隊(duì)的合作很重要，每人一個(gè)小模塊，大大加快開發(fā)效率。

總結(jié)

以上是生活随笔為你收集整理的算法设计课程设计－－任务时间表问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。