CSES动态规划题：电梯最少搭乘次数求解及双指针法失效疑问

问题描述 #

有n个人想要乘坐一栋楼里唯一的电梯上楼。已知每个人的体重以及电梯的最大允许承重，求最少需要多少次电梯搭乘。
约束条件
1 ≤ n ≤ 20
1 ≤ x ≤ 10^9
1 ≤ w_i ≤ x

双指针法出错的原因 #

你的双指针思路（排序后每次带最重的人，再尽可能塞轻的）在多数场景下能得到正确结果，但出错可能来自两个方面：

1. 数值溢出导致判断错误 #

由于体重和承重上限可达1e9，两个体重相加会超过32位整数的范围（比如1e9+1e9=2e9>2^31-1）。如果你的代码用int类型存储总重量，溢出后会变成负数，错误地判定总重量≤承重，导致违规载人，最终得到错误的次数。解决方法是用64位整数类型（比如C++的long long、Python的int）存储总重量。

2. 代码实现逻辑错误 #

大概率是你的双指针移动逻辑出错，比如：

• 排序方向错误（比如按升序处理时，错误地先取最轻的人）
• 计算剩余承重时未正确扣除已选人员的体重
• 未正确标记已搭乘的人员，导致重复计算

保证正确的解法：状态压缩DP #

因为n≤20，用状态压缩DP可以确保得到最优解，完全规避贪心策略的局限性：

• 定义dp[mask]：mask是一个二进制数，每一位表示对应人员是否已搭乘电梯，dp[mask]为该状态下的最少搭乘次数。
• 初始状态：dp[0] = 0（无人搭乘时次数为0）。
• 状态转移：遍历每个状态mask，对于所有未搭乘的人员，尝试将其加入当前电梯，同时尽可能加入其他未搭乘人员直到总重量超过承重，更新新状态的dp值。

示例Python代码：

def min_elevator_trips(weights, x):
    n = len(weights)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == float('inf'):
            continue
        # 找到第一个未搭乘的人，作为当前电梯的起始乘客
        first = -1
        for i in range(n):
            if not (mask & (1 << i)):
                first = i
                break
        if first == -1:
            continue
        # 先尝试只带这个起始乘客
        new_mask = mask | (1 << first)
        dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
        # 再尝试加入其他能装下的乘客
        remaining = x - weights[first]
        current_mask = new_mask
        for i in range(first + 1, n):
            if not (mask & (1 << i)) and weights[i] <= remaining:
                remaining -= weights[i]
                current_mask |= (1 << i)
                dp[current_mask] = min(dp[current_mask], dp[mask] + 1)
    return dp[(1 << n) - 1]

内容的提问来源于stack exchange，提问作者Sagar Pant