Java能否用仅含4个指定参数的递归方法求解符合重量限制的数组组合最高价值

完全可以通过给定参数的递归实现找到满足重量限制的最高价值，这是典型0-1背包问题的暴力递归解法，核心逻辑是对每个石头做「选/不选」的二元决策，遍历所有合法组合后取最大值。

递归逻辑说明 #

递归的两个终止条件：

• 所有石头已遍历完成（index == 0），没有可选石头，返回价值0
• 剩余可承载重量为0（maxWeight <= 0），无法再装任何石头，返回价值0

每个递归层的两个决策分支：

1. 不选当前第index-1个石头：直接递归求解前index-1个石头在当前剩余重量下的最大价值
2. 选当前第index-1个石头：仅当当前石头重量不超过剩余可承载重量时可触发该分支，总价值为当前石头价值 + 递归求解前index-1个石头在扣除当前石头重量后的剩余重量下的最大价值
3. 最终返回两个分支的价值最大值即可

实现代码 #

public static int maxValue(int[] weight, int[] price, int maxWeight, int index) {
    // 递归终止条件：没有石头可选 或者 没有剩余承重
    if (index == 0 || maxWeight <= 0) {
        return 0;
    }
    // 分支1：不选第index-1个石头
    int notPick = maxValue(weight, price, maxWeight, index - 1);
    // 分支2：选第index-1个石头，先判断重量是否足够
    int pick = 0;
    if (weight[index - 1] <= maxWeight) {
        pick = price[index - 1] + maxValue(weight, price, maxWeight - weight[index - 1], index - 1);
    }
    // 取两个分支的最大值
    return Math.max(notPick, pick);
}

示例验证 #

• 示例1输入：weight={20,5,10,30}，price={50,10,30,40}，maxWeight=25，index=4，调用方法返回结果为50，符合预期
• 示例2输入：weight={20,5,10,30}，price={50,10,30,40}，maxWeight=30，index=4，调用方法返回结果为80，符合预期

注：该递归实现为暴力枚举所有组合，时间复杂度为O(2^n)，n为石头数量，仅适合小数据量场景，大数据量下可通过记忆化搜索或者动态规划优化时间复杂度。

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