GeeksForGeeks提交与自定义输入同测试用例判题结果不一致问题排查

问题背景 #

练习分数背包问题时，提交代码到在线判题系统显示答案错误，但使用相同测试用例通过自定义输入运行时，能得到判题系统预期的结果，已排除全局/静态变量问题。

解题思路 #

• 基于价值/重量比（value/weight ratio）创建哈希表，键为比率，值为物品对象
• 按比率降序排序哈希表
• 遍历排序后的物品，若物品重量≤剩余容量则加入完整价值并减少剩余容量，否则按剩余容量取对应比例价值后结束
• 返回最终总价值

问题代码 #

### Item class for reference 
class Item:
    def __init__(self,val,w):
        self.value = val
        self.weight = w
        
class Solution:    
    def fractionalknapsack(self, W,arr,n):
        
        hashmap = {(item.value / item.weight) : item for i,item in enumerate(arr) }
        keys = list(hashmap.keys())
        keys.sort()
        sorted_hashmap = {}
        keys.reverse()
        
        for ele in keys :
            sorted_hashmap[ele] = hashmap[ele]
        
        final_ans = 0
        available_weight = W
        for ratio,item in sorted_hashmap.items() :
            if available_weight > 0 : 
                if item.weight <= available_weight :
                    final_ans += item.value
                    available_weight -= item.weight
                else :
                    final_ans += available_weight * ratio
                    break
            else :
                break
                
                    
        return final_ans

测试用例情况 #

• 输入：

  84 87
  78 16 94 36 87 43 50 22 63 28 91 10 64 27 41 27 73 37 12 19 68 30 83 31 63 24 68 36 30 3 23 9 70 18 94 7 12 43 30 24 22 20 85 38 99 25 16 21 14 27 92 31 57 24 63 21 97 32 6 26 85 28 37 6 47 30 14 8 25 46 83 46 15 18 35 15 44 1 88 9 77 29 89 35 4 2 55 50 33 11 77 19 40 13 27 37 95 40 96 21 35 29 68 2 98 3 18 43 53 7 2 31 87 42 66 40 45 20 41 30 32 18 98 22 82 26 10 28 68 7 98 4 87 16 7 34 20 25 29 22 33 30 4 20 71 19 9 16 41 50 97 24 19 46 47 2 22 6 80 39 65 29 42 1 94 1 35 15
  

• 预期输出：1078.00
• 提交输出：235.58
• 自定义输入输出：1078.00

问题分析与修复 #

核心问题 #

使用字典存储比率与物品的映射时，若多个物品的价值/重量比相同，字典的键会被覆盖，导致仅保留最后一个同比率的物品，丢失了其他同比率的物品。遍历计算时，这些丢失的物品未被计入总价值，最终导致提交结果远低于预期。

修复方案 #

直接对物品列表按价值/重量比降序排序，无需使用字典，确保所有物品都能被纳入计算。

修正后代码 #

class Item:
    def __init__(self,val,w):
        self.value = val
        self.weight = w
        
class Solution:    
    def fractionalknapsack(self, W, arr, n):
        # 按价值/重量比降序排序物品
        arr.sort(key=lambda x: (x.value / x.weight), reverse=True)
        
        final_ans = 0.0
        available_weight = W
        
        for item in arr:
            if available_weight <= 0:
                break
            # 物品能完全放入背包
            if item.weight <= available_weight:
                final_ans += item.value
                available_weight -= item.weight
            else:
                # 取部分物品
                final_ans += available_weight * (item.value / item.weight)
                available_weight = 0
        
        return final_ans

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