GeeksForGeeks 上的提交和自定义输入对同一测试用例给出不同的判断结果

Question

我正在练习 GeeksForGeeks 问题 分数背包：

给定N个物品的重量和值，我们需要将这些物品放入容量为W的背包中，以获得背包中的最大总价值。

注意：与0/1背包不同，你可以破坏物品。

示例1：

输入：

N = 3，W = 50
值[] = {60,100,120}
重量[] = {10,20,30}

输出：

240.00

解释

根据麻袋的给定容量，我们可以拥有的物品总价值为 240.00。

当我提交代码时，在线法官告诉我我的代码返回了错误的答案，但是当我在自定义输入上运行相同的测试用例时，我得到了法官预期的答案。

我搜索了为什么会发生这种情况，我遇到的潜在原因是全局/静态变量，但是我没有使用任何全局/静态变量。

我解决问题的方法是：

• 根据值/权重比率制作排序的哈希图，（键，值）对为（比率，项目）。
• 对于每件物品，如果该物品的重量小于可用重量，那么我们将直接将该值添加到最终答案中。
• 否则我们将可用权重乘以比率，将其添加到最终答案并中断。
• 最后我们会返回答案。

我正在使用的代码：

### 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

测试成功但提交失败的输入：

Input :
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

Output :
Online Judges Expected Output : 1078.00
My Submission Output : 235.58
My custom input output : 1078.00

Answer 1

这确实很令人困惑！我查看了 GeeksForGeeks 运行代码的 Python 版本，在撰写本文时，这些版本会有所不同，具体取决于您是 test 还是 submit！

• 测试代码时：Python 3.7.13
• 提交代码时：Python 3.5.2

这解释了为什么测试与提交时会得到不同的结果。由于 Python 3.6 字典按插入顺序进行迭代，但在旧版本中，迭代顺序是未定义的 - 无法保证插入项目的顺序也将是迭代项目的顺序。

退一步来说，这里你不应该需要字典。事实上，当两个项目碰巧具有相同的比例时就会出现问题，因为那样你就会失去一个。

只需按比例对输入项进行排序即可解决此问题。这是删除了 hasmap 并在输入列表上调用

sort

的代码：

class Solution:
    def fractionalknapsack(self, W, arr, n):
        arr.sort(key=lambda item: item.value / item.weight, reverse=True)
        final_ans = 0
        available_weight = W
        for item in arr:
            if available_weight > 0: 
                if item.weight <= available_weight:
                    final_ans += item.value
                    available_weight -= item.weight
                else :
                    final_ans += available_weight * item.value / item.weight
                    break
            else:
                break
        return final_ans

Answer 2

在解决no时遇到同样的问题。极客的极客中的 C 语言反转问题。