Codevs4228 DFS

Posted on | In ,

索道上的缆车最大承重量为W，而N只小猫的重量分别是 C1、C2…… CN。当然，每辆缆车上的小猫重量之和不能超过W。每 租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
(n<=18)

题解

  • 从大到小直接贪心显然是错误的。
  • 考虑枚举需要的缆车数量，dfs枚举每个小猫坐那辆缆车，如果全部小猫都可以坐上车，即满足。
  • 优化：第i只猫坐的缆车的编号j，则有i<=j
  • 时间复杂度不会算