java算法分析与设计之集装箱装载问题源代码

在 Java 中，集装箱装载问题是一个经典的优化问题，也被称为“0-1背包”问题，属于动态规划的一种应用。它的目标是最大化能够装入集装箱的物品总价值，每个物品有自己的重量和价值，同时要考虑容器的最大承重限制。

以下是一个简单的 Java 源代码片段，使用了递归回溯法来解决这个问题：

public class ContainerLoading {
    int[] weights;
    int[] values;
    int maxWeight;

    // 构造函数接收物品信息和最大承载量
    public ContainerLoading(int[] itemsWeights, int[] itemsValues, int maxContainerWeight) {
        weights = itemsWeights;
        values = itemsValues;
        maxWeight = maxContainerWeight;
    }

    // 动态规划辅助函数，尝试将当前物品放入容器
    private boolean canFit(int index, int containerWeight) {
        if (index == weights.length || containerWeight == 0) return false;
        // 如果当前物品放进去不会超过最大重量，且有更高的价值可以选择，则选择放进去
        return canFit(index + 1, containerWeight) || values[index] > values[index - 1] && containerWeight >= weights[index];
    }

    // 主函数计算最大价值
    public int getMaxValue() {
        return backtrack(0, maxWeight);
    }

    // 递归查找最优解
    private int backtrack(int start, int remainingWeight) {
        if (remainingWeight < 0) return 0; // 超过重量限制，返回0
        if (start == weights.length) return 0; // 所有物品都已处理完

        // 选择当前物品并继续剩余部分
        int valueWithItem = values[start] + backtrack(start + 1, remainingWeight - weights[start]);

        // 不选择当前物品直接继续下一件
        int valueWithoutItem = backtrack(start + 1, remainingWeight);

        return Math.max(valueWithItem, valueWithoutItem);
    }
}