这道题的正解是 加权区间调度+0/1 背包二维 DP,但是我们用朴素解法 DFS 枚举每个项目选或不选也能在考试时拿到一定的分数。
题意:有 n 个项目,每个有开始时间 s、结束时间 e、工作量 w、收益 v。所选项目两两时间不重叠(若某项目在时刻 X 结束,可立刻接在 X 开始的项目),且总工作量不超过 maxEffort,求最大收益。
朴素做法:
一个项目经理需要对项目进行计划制定,现有 n 个项目,每个项目有一个开始时间 startTime[i]、结束时间 endTime[i] 以及所需投入的人力 effort[i] ,完成每个项目能获得的收益为 profit[i] 。
项目团队可以投入的最大工作量为 maxEffort ,并且在时间上重叠的项目不能同时开展。
如果一个项目在时间 X 结束,可以立刻承接在时间 X 开始的新项目。
请编写一个函数,计算在不超过可以投入最大工作量为 maxEffort 的情况下,合理安排计划获得的最大收益。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册