Java递归电梯分组算法：基准案例理解与双约束目标实现问询

首先得说，你现在的代码逻辑和目标完全跑偏了——你要找的是不超6人、不超500kg，且载重最大的乘客组，但当前递归只是在统计“处理到第7个乘客索引”的组合数，既没检查重量约束，也没追踪最大载重，这肯定达不到需求。

先拆解现有代码的核心问题 #

1. 基准条件完全错误：你写的if (c > 6)就判定为解，但c是当前处理的乘客索引，不是已选人数啊！比如你只选了2个人，但处理到第7个乘客索引时，这个条件就会触发，完全不符合“最多6人”的约束。而且这个条件根本没检查总重量是否超过500kg，哪怕选的6个人总重600kg，也会被当成有效解输出，这显然不对。
2. 缺少最优解追踪逻辑：当前递归只是返回组合数量，完全没记录哪个组合的载重最大，根本没法完成“找最大载重”的核心目标。
3. 剪枝逻辑写反：if (sumOfUntried > target) return 0这行逻辑错误——如果剩余未选乘客的总重量还大于剩余载重（target），其实还有可能选出符合条件的组合，应该继续递归；反过来，如果当前已选重量加上剩余所有乘客的重量都比不上当前已知的最大载重，这时候才应该剪枝，因为不可能得到更优的解了。

修正思路：用递归追踪最优状态 #

要实现需求，递归时需要时刻关注三个核心状态：

• 当前处理到第几个乘客（索引）
• 已选乘客的数量（不能超过6）
• 已选乘客的总重量（不能超过500）

同时，我们需要用全局变量（或引用传递的对象）来记录：

• 当前找到的最大载重值
• 对应这个最大载重的乘客组合列表

正确的基准条件 #

递归终止条件分为两种：

1. 已超人数或载重：直接返回，这个组合无效。
2. 处理完所有乘客：如果当前组合是有效解（人数≤6、重量≤500），就对比它的总重量和当前最大载重，更新最优解。

递归分支逻辑 #

对每个乘客，我们有两种选择：

• 选这个乘客：如果选后人数不超6、总重量不超500，就更新状态（人数+1、总重量+当前体重、列表加入该体重），继续递归下一个乘客，递归结束后回溯（移除该体重，恢复状态）。
• 不选这个乘客：保持当前状态不变，直接递归下一个乘客。

剪枝优化 #

为了提高效率，提前计算剩余所有乘客的总重量：如果当前已选重量 + 剩余乘客总重量 ≤ 当前最大载重，那哪怕把剩下的乘客全选了也达不到当前最优，直接终止递归即可。

修正后的Java代码示例 #

import java.util.ArrayList;
import java.util.List;

public class ElevatorOptimalGroup {
    // 全局变量记录最优解：最大载重和对应的乘客列表
    private static int maxWeight = 0;
    private static List<Integer> bestGroup = new ArrayList<>();

    public static void main(String[] args) {
        int[] weights = {10, 30, 40, 41, 80, 90, 50, 55, 92, 66, 82, 62, 70};
        int maxPeople = 6;
        int maxLoad = 500;

        // 初始化递归：从第0个乘客开始，已选0人，总重0，空列表
        findOptimalGroup(weights, 0, 0, 0, new ArrayList<>(), maxPeople, maxLoad);

        // 输出结果
        System.out.println("最优乘客组合：" + bestGroup);
        System.out.println("总载重：" + maxWeight + "kg");
        System.out.println("人数：" + bestGroup.size() + "人");
    }

    private static void findOptimalGroup(int[] weights, int currentIndex, int currentCount, int currentWeight,
                                         List<Integer> currentGroup, int maxPeople, int maxLoad) {
        // 基准条件1：已超人数或载重，直接返回
        if (currentCount > maxPeople || currentWeight > maxLoad) {
            return;
        }

        // 基准条件2：处理完所有乘客，检查是否是最优解
        if (currentIndex == weights.length) {
            if (currentWeight > maxWeight) {
                // 更新最大载重和最优组合
                maxWeight = currentWeight;
                bestGroup = new ArrayList<>(currentGroup);
            } else if (currentWeight == maxWeight) {
                // 如果需要保存所有相同最大载重的组合，可以在这里扩展逻辑
            }
            return;
        }

        // 剪枝优化：计算剩余乘客的总重量
        int remainingTotal = 0;
        for (int i = currentIndex; i < weights.length; i++) {
            remainingTotal += weights[i];
        }
        // 如果当前重量+剩余总重量 <= 已知最大载重，没必要继续递归
        if (currentWeight + remainingTotal <= maxWeight) {
            return;
        }

        // 分支1：选择当前乘客
        currentGroup.add(weights[currentIndex]);
        findOptimalGroup(weights, currentIndex + 1, currentCount + 1, currentWeight + weights[currentIndex],
                currentGroup, maxPeople, maxLoad);
        // 回溯：移除当前乘客，恢复状态
        currentGroup.remove(currentGroup.size() - 1);

        // 分支2：不选择当前乘客
        findOptimalGroup(weights, currentIndex + 1, currentCount, currentWeight,
                currentGroup, maxPeople, maxLoad);
    }
}

代码说明 #

• 用maxWeight和bestGroup全局变量追踪最优解，避免递归中频繁传递复杂对象；
• 递归状态清晰传递当前处理索引、已选人数、已选重量和已选列表；
• 剪枝逻辑有效减少不必要的递归调用，提升效率；
• 运行后会输出符合要求的最大载重组合（根据提示，会找到超过470kg的有效解）。

内容的提问来源于stack exchange，提问作者Luis E.