knapsack 代码在 GFG 中提交时无法在 python 中运行

Question

背包代码无法工作。其中一个测试用例失败。

我有

#User function Template for python3
t=[[ -1 for j in range(1001)] for i in range(1001)]
class Solution:
    
    #Function to return max value that can be put in knapsack of capacity W.
    def knapSack(self,W, wt, val, n):
       
        # code here
        
        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):
        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

尝试了多种方法但不起作用。我想要 memozation tecnequi 中的解决方案。请查看并告诉我为什么它不起作用。请在memozation中说出答案。我已经知道自上而下的方法答案。

Answer 1

问题在于全局

t

变量：它将用于多个测试用例，因此一次运行的结果将泄漏到下一次运行中。

您需要将

t

设为

Solution

的实例成员（假设 GFG 为每次运行实例化一个新的

Solution

对象），或者将其设为局部变量并在递归部分使用局部函数。算法。

不是问题，但是：

• 我在递归函数末尾只有一个

  return

  语句，因为它对于所有三种情况都是相同的。

• elif

  可以只是

  else

  ，因为它应该涵盖其余的情况

这是第二种方法的样子：

class Solution:
    
    def knapSack(self, W, wt, val, n):
        # Define the memoization structure locally, so it is reset for every run:
        t = [ [-1 for j in range(W + 1)] for i in range(n + 1) ]
        
        def knapSackHelper(W, n):
            if n == 0 or W == 0:
                return 0
            if t[n][W] == -1:
                if wt[n-1] <= W:
                    t[n][W] = max(val[n-1] + knapSackHelper(W - wt[n-1], n-1), 
                                  knapSackHelper(W, n-1))
                else:
                    t[n][W] = knapSackHelper(W, n-1)
            return t[n][W]
            
        return knapSackHelper(W, n)