1)题目意思
有 N 头奶牛要坐电梯下楼。每头奶牛体重 Ci,电梯每次最多承重 W。
你可以把若干头奶牛一起放进一次电梯里,但这次电梯里所有奶牛体重之和不能超过 W。问:把所有奶牛都运下去,最少需要坐几次电梯。
N <= 18,可以用状态压缩 DP。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2)思路解析(状态压缩 DP:最少趟数 + 当前趟已用重量)
我们用 mask 表示已经运下去的奶牛集合:
* mask 的第 i 位为 1 表示第 i 头奶牛已经安排好了
对每个 mask,我们记录一个最优状态:
* dp[mask] = (rides, weight)
* rides:已经用了多少趟电梯
* weight:当前最后一趟电梯已经放了多少重量(越小越好,方便后面再塞人)
初始:
* dp[0] = (1, 0)
表示从第 1 趟开始装,当前重量为 0
转移:枚举一个还没装的奶牛 i
* 如果 weight + Ci <= W:可以塞进当前这趟
新状态是 (rides, weight + Ci)
* 否则:必须开新的一趟
新状态是 (rides + 1, Ci)
每次取更优的状态,比较规则:
1. rides 更小更优
2. rides 相同,则 weight 更小更优
答案是 dp[(1<<N)-1].rides。
复杂度:
* 状态数 2^N,每个状态枚举 N 个奶牛
* N<=18,可以通过
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3)代码