知识卡片
带截止期任务的收益
单机任务各有处理时长、收益和截止期,任务不可抢占;只有在截止期前完成才取得收益。
优化问题要安排全部任务的顺序,使所得收益最大。
改变为判定问题时应再给收益门槛,不能把该练习要求误记成已完成的NP完全证明。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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