会员专享
请先
登录,登录后可使用今日免费解锁;
开通会员后可解锁完整内容。
DFS暴力解法
这道题的正解是 折半搜索(Meet in the Middle),但是我们用朴素解法 DFS 枚举每个需求选或不选也能在考试时拿到一定的分数。
题意:有 n 个需求,第 i 个需要 ti 人天,预算为 T。每个需求要么全做要么不做,求不超过 T 的最大工作量之和。
朴素做法:对每个需求做或不做,DFS 枚举全部 2n 种方案,在不超过 T 的方案里取最大和。
n 较小时可过;题面 n≤40,直接 240 会超时,需要折半。
开通会员即可查看完整视频题解: 1.题目讲解 2.思路分析 3.逐行代码手写