算法大作业一任务选择与安排

算法大作业一：任务选择与安排（要求写详细的报告，提交电子版）问题如下：现有一组(n个任务，执行其中任何一个任务，恰好需要1分钟。假设任务的执行从第0（i=1,2,。。。,nd(i)能够在截止时间第d(i)分钟之前完成（含d(i)），则执行任务能够获得p(i)的效益；若任务的完成时间超过了截止时间d(i)0。显然，在此情况下任务不应该被执行。现要从n个任务选出若干个（必要时可以全选），并安排这些任务的执行次序，使得依次完成这些任务后，所获效益值的总和为最大。例如，若一组（共4个）任务的d,p值分别为：d(1)=1;p(1)=3;d(2)=1;p(2)=2;d(3)=2;p(3)=4;d(4)=2;p(4)=5；3再执行任务（或先执行任务4后执行任务），最优解的总效益值为9。为更好地理解该问题的本质，我们将上例进行扩展：d(5)=3;p(5)=2;d(6)=4;p(6)=7;d(7)=4;p(7)=5;d(8)=6;p(8)=1。（可以把两个数组用表格画出来，这样比较形象直观，以便对设计算法提供帮助。）请完成下列工作：1、执行次序、最终获得的总效益值）。（说明：可以用伪代码，但要用自然语言详细说明具体的算法思想，或者用流程图表达具体的算法思想。对算法中所使用的结构、数组和变量等，也要对其作用进行说明。）2、对你所设计的算法进行分析，给出在最坏情况下的时间复杂度。3、试证明：你所设计的算法在执行过程中，始终保持了最优性。S={i,i,。。。i（诸ik≤n且已确定），12kj对S中的诸任务，如果能够找到一种执行次序，使得每个任务都能在其规定的截止时间内完成，则称S是一个有效子集。试完成下面的工作：4、设计一个时间复杂度低的算法，该算法能够判定出所给任务子集S是否为有效子集。其次，该算法的时间复杂度是多少？（相对前3问，第4问比较容易，可以仅用自然语言描述你的算法思想。）解：根据题意，画出表格：11212324425532647745861d(i)P(i)3其中表示第个任务。1、经分析得，按照任务截止时间降序遍历的贪心算法可以得到该问题的最优解。n=8时如表所示：第6分钟时：只能完成任务8，效益为P=11-7作为一个整体继续遍历第5分钟时：没有可完成任务，所以后面完成的任务提前1分钟，完成任务8，效益为P=1。则任务1-7作为一个整体继续遍历第46或者7，根据贪心算法，p(6)>p(7)6，获得总效益为P=p(8)+p(6)=8，则任务1-5，7作为一个整体继续遍历第35或者任务7，根据贪心算法，p(5)<p(7)7，获得总效益为P=p(8)+p(6)+p(7)=13,则任务1-5作为一个整体继续遍历第2分钟：可以完成任务2，3，5，根据贪心算法，p(4)>p(3)>p(5)，所以完成任务4，获得效益为P=p(8)+p(6)+p(7)+p(4)=18，则任务1-3，5作为一个整体继续遍历第1分钟：可以完成任务1，2，35，根据贪心算法，p(3)>p(1)>p(2)=p(5)，所以完成任务3，获得效益为P=p(8)+p(6)+p(7)+p(4)+p(3)=22。至此整个运行时间结束。由以上得，n=8时，选择执行的任务：3，47，6，8；执行次序：，4，7，68；获得效益P=22。当nn个任务的截止时间d(i)i=123...n这里我们选择堆排序，按照截止时间从小到大对每个任务进行重新编号。不难得到max(d)=d(n);我们给算法起个名字，叫GreedyTaskschedule(n)。而且由题意知，对于n个任务，每个任务1分钟，则完成n个任务共需分钟。为了方便，我们声明一个变量j=0。第n分钟时：可以完成一个所有截止时间不小于n的任务D1，如果为空，则此分钟不执行任务，。否则对D1中的所有任务的效益进行排序，找出最大值。这里使用大顶堆排序算法，得到D1中效益最大的P(a1)，a1为D1截止时间不小于n的所有任务中效益最高的任务。如果出现两个或更多任务，则选择截止时间较小的任务。所以P=p(a1)，对除a1外的其他任务遍历。第n-1a1外截止时间不小于n-1的任务D2D2为空，则后面需要执行的任务前移1分钟执行。否则对D2中所有任务效益进行大顶堆排序，找出最大值p(a2)P=p(a1)+p(a2)...第n-i{a1a2a外截止时间不小于n-i的任务，如果i-j为空，则从第n-1+i分钟到第n分钟需要执行的i-1个任务前依次移1分钟执行，，否则对Di{中的所有任务效益进行大顶堆排序，找出最大值p(ai)，所以P=p(a1)+...+p(ai)...第1分钟时：可以完成一个除{a1，a2,a外截止时间为不小于1的任务Dn-1，如果n-j-1Dn-1为空，则从第2n分钟执行的任务前移1分钟执行。否则对Dn-1中所有任务效益进行大顶堆排序，找出最大值p(a，总效益为P=p(a1)+...+p(a)n-jn-j以上就是当n不确定时的算法思想。选择执行的任务为a1，a2，a3...a执行次序为：n-jnja1，a2，a3...a，最终总效益为p(ai)n-ji12、堆排序在最坏情况下的算法时间复杂度为O(nlogn)。算法在进行截止时间排序时采用的堆排序。查找满足条件的任务的时间复杂度是O(1)。找出满足条件的效益最大的任务。采用的是大顶堆排序，时间复杂度为O(logn)。每分钟都执行一次大顶堆排序，一共n分钟，所以求最大效益的时间复杂度为O(nlogn)。所以该算法在最坏情况下的时间复杂度为O(nlogn)。3、对于贪心算法的最优性证明，我打算从两个方面，分别是贪心选择性和优化子结1>贪心选择性。对于该任务集，设为A，设S为最优解集合。第n分钟完成一个截构。止时间不小于n的任务D1。假设D1不为空，则第n分钟必须要完成一个D1中截止时间最大的任务a1。只需证明存在任务集A的一个最优解a1，第n分钟时执行任务a1可以获得最大效益。设ak为第na1=aka1≠ak，在第n分钟所选择的任务D1中效益最大的任务为a1a1必等于ak。2>优化子结构。只需证明a1为第n分钟所要执行的任务，则S-{a1}为n-1内分钟所S-{a1}不是n-1是n-1分钟内所要执行的任务集合，则P(X)<P(S-{a1})，则P(X)+P(a1)<P(S)。这与S为最优解结合的假设相矛盾。故S-{a1}是第n-1分钟内所要执行的任务集合。4、EffectiveSubset(k)算法可以满足题目要求。经分析得，我们可以找截止时间最大的任务，以此为切入点进行算法设计。因为子集S={i，i...i中共k个任务，则执行个任务所需要的时间为分钟。对S中12k的元素按照截止时间由小到大进行堆排