基于动态规划求解带ID与阻力限制的容器堆叠最大化问题

问题描述 #

给定一组按ID排序的容器（每个容器包含id、weight、resistance属性），需找到最高的容器堆叠，满足以下限制：

• 容器不能放置在ID更大的容器上方（即堆叠顺序从上到下ID递减）
• 任意容器上方所有容器的总重量不得超过该容器的resistance

示例：容器集合为{Container(1,3,3), Container(2,10,2), Container(3,10,2), Container(4,1,2), Container(5,2,12)}，最优堆叠（从上到下）为5、4、1。

当前实现困境 #

已通过递归+记忆化方法解决该问题，但动态规划实现中无法正确处理阻力随上方容器重量变化的逻辑，当前代码如下：

public static List<Container> findBestPile(List<Container> containers){
    int n = containers.size();
    int[] dp = new int[n];
    int[] previous = new int[n];
    int[] resistance = new int[n];
        
    Arrays.fill(dp, 1);
    Arrays.fill(previous, -1);
        
    for(int i = 0; i < n; i++) resistance[i] = containers.get(i).resistance;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // 验证i能否放在j的上方
            if (containers.get(i).weight <= resistance[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                previous[i] = j;
                resistance[i] = Math.min(resistance[j] - containers.get(i).weight, containers.get(i).resistance);
            }
        }
    }
    // 找到dp数组中最大值的索引
    int maxIndex = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[maxIndex]) {
            maxIndex = i;
        }
    }

    // 从previous数组重建最优堆叠
    List<Container> bestPile = new ArrayList<>();
    for (int i = maxIndex; i != -1; i = previous[i]) {
        bestPile.add(containers.get(i));
    }

    return bestPile;
}

问题分析 #

当前DP实现的核心缺陷：

• 用单一resistance[i]记录状态完全不够——同一个容器i在不同堆叠路径下，剩余可承载重量差异极大，只保留一种状态会丢失关键信息，导致无法覆盖最优路径的可能性。
• 以示例中的容器1为例，它需要被放在4和5下方，但当前逻辑无法追踪到"5→4→1"这条路径中，每个容器的剩余阻力变化过程。

修正方案 #

重新定义DP状态，为每个容器保留所有可能的剩余承载能力-堆叠高度组合，避免状态丢失：

修正后的代码实现 #

import java.util.*;

class Container {
    int id;
    int weight;
    int resistance;

    public Container(int id, int weight, int resistance) {
        this.id = id;
        this.weight = weight;
        this.resistance = resistance;
    }

    @Override
    public String toString() {
        return "Container(" + id + "," + weight + "," + resistance + ")";
    }
}

public class ContainerStack {
    static class State {
        int height;
        int remainingResistance;
        int prevIndex;
        int prevRemaining;

        State(int height, int remainingResistance, int prevIndex, int prevRemaining) {
            this.height = height;
            this.remainingResistance = remainingResistance;
            this.prevIndex = prevIndex;
            this.prevRemaining = prevRemaining;
        }
    }

    public static List<Container> findBestPile(List<Container> containers) {
        int n = containers.size();
        // 每个容器对应一组状态：剩余阻力 -> 最优状态（高度、前驱信息）
        List<Map<Integer, State>> dp = new ArrayList<>();
        int maxHeight = 0;
        int bestIndex = 0;
        int bestRemaining = 0;

        for (int i = 0; i < n; i++) {
            Map<Integer, State> currentStates = new HashMap<>();
            // 初始状态：仅当前容器，剩余阻力为自身resistance，高度为1
            currentStates.put(containers.get(i).resistance, new State(1, containers.get(i).resistance, -1, 0));
            dp.add(currentStates);

            // 遍历所有ID更小的容器j，尝试将i堆叠在j上方（ID小的容器在下方）
            for (int j = 0; j < i; j++) {
                Container iContainer = containers.get(i);
                // 遍历j的所有可能状态
                for (Map.Entry<Integer, State> jEntry : dp.get(j).entrySet()) {
                    int jRemaining = jEntry.getKey();
                    State jState = jEntry.getValue();
                    // 检查i的重量是否在j的剩余承载范围内
                    if (iContainer.weight <= jRemaining) {
                        int newRemaining = Math.min(jRemaining - iContainer.weight, iContainer.resistance);
                        int newHeight = jState.height + 1;
                        // 若当前剩余阻力状态未记录，或新高度更高，则更新
                        if (!currentStates.containsKey(newRemaining) || newHeight > currentStates.get(newRemaining).height) {
                            currentStates.put(newRemaining, new State(newHeight, newRemaining, j, jRemaining));
                            // 更新全局最优解
                            if (newHeight > maxHeight) {
                                maxHeight = newHeight;
                                bestIndex = i;
                                bestRemaining = newRemaining;
                            }
                        }
                    }
                }
            }
        }

        // 回溯重建堆叠路径
        List<Container> bestPile = new ArrayList<>();
        int currentIndex = bestIndex;
        int currentRemaining = bestRemaining;
        while (currentIndex != -1) {
            bestPile.add(containers.get(currentIndex));
            State currentState = dp.get(currentIndex).get(currentRemaining);
            currentIndex = currentState.prevIndex;
            currentRemaining = currentState.prevRemaining;
        }
        // 反转得到从上到下的堆叠顺序
        Collections.reverse(bestPile);
        return bestPile;
    }

    public static void main(String[] args) {
        List<Container> containers = Arrays.asList(
                new Container(1, 3, 3),
                new Container(2, 10, 2),
                new Container(3, 10, 2),
                new Container(4, 1, 2),
                new Container(5, 2, 12)
        );
        List<Container> result = findBestPile(containers);
        System.out.println("最优堆叠（从上到下）：");
        result.forEach(System.out::println);
    }
}

代码说明 #

• 使用List<Map<Integer, State>>存储每个容器的所有可能状态，Map的键为剩余可承载重量，值为对应的堆叠高度和前驱信息，确保所有可行路径都被记录。
• 对每个容器i，先初始化自身的独立状态，再遍历所有ID更小的容器j，尝试将i堆叠在j上方，更新i的状态集合。
• 回溯时从全局最优状态出发，反向追踪完整路径，最后反转得到符合要求的从上到下的堆叠顺序。

复杂度说明 #

• 时间复杂度：O(n² * k)，其中k是每个容器的平均状态数，实际场景中k不会过大（剩余阻力为有限整数）。
• 空间复杂度：O(n * k)，用于存储每个容器的状态集合。

内容的提问来源于stack exchange，提问作者Nombre de Usuario Genérico