Python版0-1背包记忆化代码提交GFG失败问题排查

问题根源 #

你的代码中，全局定义的t数组在多测试用例场景下不会自动重置。第一个测试用例运行后，t数组中已经存储了该测试用例的计算结果；当第二个测试用例执行时，代码会直接复用t数组里的旧值，而非重新计算当前测试用例的结果，这就导致了错误。

修复方案 #

以下两种方式任选其一即可：

方式1：每次测试用例执行前重置全局t数组 #

在测试用例循环内，每次创建Solution实例前，重新初始化t数组：

#User function Template for python3

class Solution:
    #Function to return max value that can be put in knapsack of capacity W.
    def knapSack(self,W, wt, val, n):
        global t
        if n==0 or W==0:
            return 0
        if t[n][W]!=-1:
            return t[n][W]
        if wt[n-1]<=W:
            t[n][W]=max(val[n-1]+self.knapSack(W-wt[n-1], wt, val, n-1), 
            self.knapSack(W, wt, val, n-1))
            return t[n][W]
        elif wt[n-1]>W:
            t[n][W]=self.knapSack(W, wt, val, n-1)
            return t[n][W]
            
#{ 
 # Driver Code Starts
#Initial Template for Python 3
import atexit
import io
import sys

# Contributed by : Nagendra Jha

if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        # 每次测试用例前重置记忆化数组
        t=[[ -1 for j in range(1001)] for i in range(1001)]
        n = int(input())
        W = int(input())
        val = list(map(int,input().strip().split()))
        wt = list(map(int,input().strip().split()))
        ob=Solution()
        print(ob.knapSack(W,wt,val,n))
# } Driver Code Ends

方式2：将t改为类实例变量，每次创建实例时初始化 #

避免使用全局变量，把t作为Solution类的实例变量，每次创建ob时都会重新初始化：

#User function Template for python3

class Solution:
    def __init__(self):
        # 初始化记忆化数组
        self.t=[[ -1 for j in range(1001)] for i in range(1001)]
    
    #Function to return max value that can be put in knapsack of capacity W.
    def knapSack(self,W, wt, val, n):
        if n==0 or W==0:
            return 0
        if self.t[n][W]!=-1:
            return self.t[n][W]
        if wt[n-1]<=W:
            self.t[n][W]=max(val[n-1]+self.knapSack(W-wt[n-1], wt, val, n-1), 
            self.knapSack(W, wt, val, n-1))
            return self.t[n][W]
        elif wt[n-1]>W:
            self.t[n][W]=self.knapSack(W, wt, val, n-1)
            return self.t[n][W]
            
#{ 
 # Driver Code Starts
#Initial Template for Python 3
import atexit
import io
import sys

# Contributed by : Nagendra Jha

if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        n = int(input())
        W = int(input())
        val = list(map(int,input().strip().split()))
        wt = list(map(int,input().strip().split()))
        ob=Solution()
        print(ob.knapSack(W,wt,val,n))
# } Driver Code Ends

说明 #

两种方式的核心都是确保每个测试用例都使用全新的、初始化为-1的记忆化数组，避免不同测试用例的缓存结果互相干扰。这样就能解决你遇到的“单独运行测试用例正常，批量提交失败”的问题。

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