返回
当前 - 选择题 - 动态规划
困难
题号:0120150500046
单选题
2015年5月第46题

某团队希望在未来18天内串行选做若干个作业。供选各作业所需的实施时间(天数)、截止时间(最迟必须在指定的数天内完工)以及利润见下表:

该团队只要能适当选择若干个作业依次实施,就能获得最大利润(25)万元。

问题(1)
浓缩知识点
知识点

带截止期的单机作业选择最大化利润问题属于典型的资源调度类动态规划问题,适用于单机串行执行、作业需在截止期前完成且目标为总利润最大化的场景。解决这类问题的核心步骤为:先将所有作业按截止期从小到大排序,优先处理时间限制更严格的任务;再采用一维动态规划数组优化求解,定义dp[t]表示累计用时为t时能获得的最大利润,针对每个作业,从其截止期倒推至作业所需时长的范围,通过dp[t] = max(dp[t], dp[t-作业时长]+作业利润)的状态转移方程更新数组,逆序更新可避免同一作业被重复选取。这类问题可拓展至多机调度、允许延误但有惩罚成本的变体场景,在项目排期、生产任务分配、自由职业者接单规划等实际场景中均有广泛应用,核心是在时间资源约束下,通过动态规划枚举可行任务组合,筛选收益最优方案。

正确答案
C

本题考察的是带截止期的作业选择问题(单机、不可延误、最大化利润)的动态规划。
按截止期从小到大排序各作业;设dp[i][t]表示在只考虑前i个作业、总用时为t且t不超过第i个作业截止期时的最大利润,转移为:dp[i][t]=max(dp[i−1][t], dp[i−1][t−p_i]+w_i),其中需满足t≤d_i与t−p_i≥0。用一维数组按t从d_i到p_i逆序更新即可。

将作业按截止期升序排序并依次做DP,得到在总时长不超过18天时的最大利润为25。回溯可得最优组合为:T5(7天, 截止10, 利润8) + T3(3天,14,5) + T2(3天,15,6) + T7(3天,16,4) + T4(2天,18,2)。按截止期顺序执行时的累计工期分别为7、10、13、16、18,均不超过相应截止期,
因此可行;总利润为8+5+6+4+2=25。
因此,答案选择C. 25。

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有