为什么以下2个代码(类似的实现)给出不同的答案测试用例?

Question

我需要解决下面的背包问题，以最大化价值，同时保持在背包的重量w

• n为可用项数
• W为背包的载重量
• wt为n项
的权重向量
• val为n项
的值向量。

我实现了以下2个代码。第一个是给我正确的响应(216)，然而第二个是给我205，但216是我应该得到的测试用例如下。(两个代码的小测试用例都能正常工作。)

两个代码都建立在相同的基础上。有人能解释一下为什么第二个给了我前面提到的测试用例的错误响应吗?

n = 29
W = 41
val = [57, 95, 13, 29, 1, 99, 34, 77, 61, 23, 24, 70, 73, 88, 33, 61, 43, 5, 41, 63, 8, 67, 20, 72, 98, 59, 46, 58, 64]
wt = [83, 84, 85, 76, 13, 87, 2, 23, 33, 82, 79, 100, 88, 85, 91, 78, 83, 44, 4, 50, 11, 68, 90, 88, 73, 83, 46, 16, 7]

代码1

#Function to return max value that can be put in knapsack of capacity W.
def knapSack(W, wt, val, n):

# code here
def hlpr(W, wt, val, n, d):
if (n == 0):
return 0
if ((W, n) in d.keys()):
return(d[(W, n)])
if (W < wt[n-1]):
d[(W, n)] = hlpr(W, wt, val, n-1, d)
else:
d[(W, n)] = max(val[n-1] + hlpr(W-wt[n-1], wt, val, n - 1, d),
hlpr(W, wt, val, n-1, d))
return(d[(W, n)])

d = {}
return(hlpr(W, wt, val, n, d))

代码2

def knapSack(W, wt, val, n):

# code here
def helper(W, wt, val, n, d, op):
if(n == 0):
return op
if((W, n) in d):
return d[(W, n)]
if(W - wt[n-1] < 0):
d[(W, n)] = helper(W, wt, val, n-1,d, op)
return d[(W, n)]
d[(W, n)] = max(helper(W-wt[n-1], wt, val, n-1, d, op+val[n-1]), helper(W, wt, val, n-1, d, op))
return d[(W, n)]
d = {}
return helper(W, wt, val, n, d, 0)

Answer 1

我们可以先通过去掉权重来简化问题>因为背包的容量是41。这将把问题减少到如下:

n = 8

W = 41

val = [1,3,77,61,41,8,58,64]

wt = [13,2,23,33,4,11,16,7]

现在，如果我们在调试这两个代码的同时监视字典，我们可以看到，

第一个代码在它的字典中保存了以下内容:

d[(W, n)] = k

对于容量W和元素个数n([0到(n-1)]个元素)，我们能得到的最优值为k

与第二段代码一样，它将以下内容保存在字典中:

d((W, n)] = k

这里k =我们可以得到的最优值(容量W下有n个元素)+从最后一个元素遍历到第n个元素得到的值op

这导致从字典中查找一系列错误。

这导致在第二个代码中这个测试用例的错误答案。