我记忆的背包 O/1 问题导致一些测试用例的答案比预期的要小。
Test case
maxWeight = 1000
weights = [3,68,24,80,76,9,24,2,46,75,56,41,95,46,23,34,64,76,6,48,25,73,87]
values =[38,16,29,47,22,25,17,49,15,15,75,11,56,99,51,92,59,37,13,98,61,50,32]
def dynamicProgramming(self,weights,values,maxWeight,currValue,index,dp):
if index < 0:
return currValue
item_weight = weights[index]
if (index,maxWeight) in dp:
return dp[(index,maxWeight)]
if item_weight > maxWeight:
skip_item = self.dynamicProgramming(weights,values,maxWeight,currValue,index - 1,dp)
dp[(index,maxWeight)] = skip_item
return skip_item
else:
new_val = currValue + values[index]
remaining_weight = maxWeight-item_weight
dp[(index,maxWeight)] = max(self.dynamicProgramming(weights,values,remaining_weight,new_val,index - 1,dp),self.dynamicProgramming(weights,values,maxWeight,currValue,index - 1,dp))
return dp[(index,maxWeight)]
当我没有将更新值作为参数传递给函数，而是将值添加到返回的调用时，我得到了正确的答案。
dp[(index,maxWeight)] = max(values[index] + self.dynamicProgramming(weights,values,remaining_weight,new_val,index - 1,dp),self.dynamicProgramming(weights,values,maxWeight,currValue,index - 1,dp))
并更新基本情况以返回 0。为什么将更新后的值作为参数传递给函数会导致错误答案？