可以用贪心算法来调度在一间演讲厅里举行的n场报告t1，t2，…，tn，假设报..._考试资料网

网站首页考试题库模拟考场智能家居网课试题

大学试题

题库首页每日一练章节练习

问答题可以用贪心算法来调度在一间演讲厅里举行的n场报告t1，t2，…，tn，假设报告在时间bj开始并在时间ej结束（两个报告不能同时进行，一个报告可以在另一个报告结束时开始），假设按照结束时间非降的顺序列出报告，得到e1≤e2≤…≤en，贪心算法这样进行：在每个阶段，从所有已经安排好的报告结束之后才开始的那些报告中，选择具有最早结束时间的报告（这个算法总是加入具有最早结束时间的报告）．请证明此贪心算法在下列意义下是最优的，即该算法总是安排尽可能多的报告．

参考答案：

您可能感兴趣的试卷

你可能感兴趣的试题

1.问答题将公式（￢p→q）∧r化成与之等值且仅含{￢，→}中联结词的公式。

参考答案：

2.问答题设n是正整数．证明：可以用L形状的碎片（一次覆盖3个格）来铺满去掉任意1个格的“2×2”棋盘．

参考答案：

3.填空题已知2个连通分支的平面图G的对偶图G^*的阶数n^*=4，边数m^*=9，则G的阶数n=（）。

参考答案：8

4.问答题证明在完全二部图K_r，s中，β₁=α₀，β₀=α₁。

参考答案：

5.填空题n（n≥4）阶轮图Wn的支配数γ₀=（）。

参考答案：1

6.问答题 求证：关于x，y的方程x+2y=n的自然数解的组数r（n）的等于

参考答案：

7.填空题n（n≥3）阶无向树的点连通度k=（）。

参考答案：1

8.问答题证明在完全图K_n（n≥3）中，β₁<α₀，β₀<α₁。

参考答案：

9.填空题无向完全图K₄的非同构的连通的生成子图共有（）个。

参考答案：6

10.问答题 求证：对任意集合A，B，C有=AⓧB

参考答案：