求解最大可收集苹果数的排序贪心算法返回错误结果排查

你得到错误结果由两类问题导致：

代码书写错误 #

• 排序比较函数逻辑错误：计算j项权重时，错误使用i项的步数作为分母，代码为nextRatio := rooms[j].numberOfApples / rooms[i].steps，正确分母应为rooms[j].steps，直接导致排序结果完全混乱。
• 变量名不一致：定义的累计步长变量为steps，循环累加时却写为step += rooms[index].steps，会触发编译错误或步长计算错误。
• 整数除法精度丢失：如果numberOfApples和steps为整数类型，直接相参会截断小数，权重计算不准，排序结果不可靠。

算法选型错误 #

你采用的「单位步长苹果数从高到低优先选择」是分数背包的最优解法，仅当允许拆分选择（比如走一半路程拿一半苹果）时生效。但当前规则是每个房间要么完整访问（拿全部苹果、消耗全额步数），要么不访问，属于标准0-1背包问题，贪心策略无法保证得到全局最优解。

反例：假设max_steps=10，三个房间分别为「6步8个苹果（单位收益~1.33）」「5步5个苹果（单位收益1）」「5步5个苹果（单位收益1）」。按贪心策略会优先选第一个房间，最终仅拿到8个苹果；但选择后两个房间可拿到10个苹果，收益更高。

采用0-1背包动态规划思路求解：

1. 定义dp数组，dp[s]表示累计消耗s步时能收集到的最大苹果数，初始值全为0。
2. 遍历所有房间，对每个房间倒序遍历步长（避免重复选择同一个房间），更新状态：如果当前步长s足够访问该房间，比较「不访问该房间的原有收益」和「访问该房间的收益（即s减去该房间步数时的最大收益加当前房间苹果数）」，保留较大值。
3. 遍历完成后，dp数组中的最大值就是所求结果。

参考实现代码：

type Room struct {
    numberOfApples int
    steps          int
}

func calculateMaxApples(rooms []Room, maxSteps int) int {
    dp := make([]int, maxSteps+1)
    for _, room := range rooms {
        // 0-1背包需要倒序遍历步长，防止同个房间被多次选择
        for s := maxSteps; s >= room.steps; s-- {
            if dp[s-room.steps]+room.numberOfApples > dp[s] {
                dp[s] = dp[s-room.steps] + room.numberOfApples
            }
        }
    }
    maxCount := 0
    for _, count := range dp {
        if count > maxCount {
            maxCount = count
        }
    }
    return maxCount
}

针对你给出的示例数据，传入maxSteps=100时，计算得到的最大苹果数为26，你之前运行得到26是代码bug下的巧合结果，并非逻辑正确得到的，更换测试用例就会暴露错误。

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