知识卡片

普通读书笔记卡 · 3722

带截止期任务的收益

理解等级:初级

单机任务各有处理时长、收益和截止期,任务不可抢占;只有在截止期前完成才取得收益。

优化问题要安排全部任务的顺序,使所得收益最大。

改变为判定问题时应再给收益门槛,不能把该练习要求误记成已完成的NP完全证明。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      Each task aj requires tj time units on the computer (its processing time), yields a profit of pj, and has a deadline dj. The computer can process only one task at a time, and task aj must run without interruption for tj consecutive time units. If task aj completes by its deadline dj, you receive a profit pj. If instead task aj completes after

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[130000,135000))。 - 结论依据:原文归约策略、习题定义与脚注限定;图34.20–34.21已核对,习题未给出的证明不作既成结论。 - 原始内容:Each task a j requires t j time units on the computer (its processing time), yields a profit of p j , and has a deadline d j . The computer can process only one task at a time, and task a j must run without interruption for t j consecutive time units. If task a j completes by its deadline d j , you receive a profit p j . If instead task a j completes after