《中科大 算法导论作业答案3.doc》由会员分享，可在线阅读，更多相关《中科大 算法导论作业答案3.doc（21页珍藏版）》请在金锄头文库上搜索。
1、第8次作业答案16.1-1 16.1-216.2-216.2-416.3-233D:编程开发VS2010myProgram经典算法大全练手题1_整数划分Interger_PartitionInterger_Partition54D:编程开发VS2010myProgram经典算法大全练手题1_整数划分Interger_PartitionInterger_Partition16.3-4 第9次参考答案16.2-5贪心算法实现，证明不能少，参考答案：16.4-1证明中要三点：1.有穷非空集合 2.遗传性 3.交换性第10次作业参考答案16.5-1题目表格：ai1234567di4243146wi10
2、203040506070解答：解法1：使用引理16.12性质（2），按wi单调递减顺序逐次将任务添加至Nt（A），每次添加一个元素后，进行计算，计算方法：Nt（A）中有i个任务时计算N0 (A),Ni(A)，其中如果存在Nj (A)j,则表示最近添加的元素是需要放弃的，从集合中删除；最后将未放弃的元素按di递增排序，放弃的任务放在所有未放弃任务后面，放弃任务集合内部排序可随意。解法2：设所有n个时间空位都是空的。然后按罚款的单调递减顺序对各个子任务逐个作贪心选择。在考虑任务j时，如果有一个恰处于或前于dj的时间空位仍空着，则将任务j赋与最近的这样的空位，并填入;如果不存在这样的空位，表示放弃。
3、答案（a1，a2是放弃的）：or 划线部分按上表di递增的顺序排即可，答案不唯一 16.5-2（直接给个计算例子说的不清不楚的请扣分）题目：本题的意思是在O(|A|)时间内确定性质2（性质2：对t=0，1，2，n，有Nt(A)=t, Nt(A)表示A中期限不超过t的任务个数）是否成立。解答示例： 思想：建立数组an,ai表示截至时间为i的任务个数，对0=ii,则说明A不独立，否则A独立。 伪代码：int temp=0; for(i=0;in;i+) ai=0; *O(n)= O(|A|) for(i=0;in;i+) adi+; *O(n)= O(|A|) for(i=0;ii）/Ni(A)i A不独立； 17.1-1（这题有歧义，不扣分）a) 如果Stack Operations包括Push Pop MultiPush,答案是可以保持,解释和书上的Push Pop MultiPop差不多.b) 如果是Stack Operations包括Push Pop MultiPush MultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替的话,平均就是O(K).17.1-2 本题目只要证明可能性，只要说明一种情况下结论成立即可
