将缓存数组添加到递归背包解决方案？

Question

我熟悉的朴素递归解决方案。然而，这个解决方案只是吐出在给定重量限制的情况下可以存储在背包中的最大值。我想做的是添加某种形式的元数据缓存（即选择了哪些项目have/not，使用“one-hot”数组[0,1,1]）。

这是我的尝试：

class Solution:
    def __init__(self):
        self.array = []
    
    def knapSack(self,W, wt, val, n): 
        index = n-1 
        if n == 0 or W == 0 : 
            return 0
        if (wt[index] > W): 
            self.array.append(0)
            choice = self.knapSack(W, wt, val, index) 

        else: 
            option_A = val[index] + self.knapSack( W-wt[index], wt, val, index)
            option_B = self.knapSack(W, wt, val, index)
            if option_A > option_B:
                self.array.append(1)
                choice = option_A
            else:             
                self.array.append(0)
                choice = option_B

        print(int(option_A > option_B)) #tells you which path was traveled
        return choice

  # To test above function 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val) 
# print(knapSack(W, wt, val, n))
s = Solution()
s.knapSack(W, wt, val, n)
>>>
1
1
1
1
1
1

220

s.array
>>>
[1, 1, 1, 1, 1, 1]

如您所见，s.array returns [1,1,1,1,1,1] 这告诉了我一些事情。 (1)，即使问题集中只有三个项目，knapSack 方法已为每个项目调用两次，并且 (2) 这是因为每个项目都流经方法中的 else 语句，所以 option_A 和 option_B 分别为每个项目计算（解释为什么数组长度是 6 而不是 3。）

我很困惑为什么在每个递归循环中都附加了 1。索引为 0 的项目不会在最优解中被选中。要回答这个问题，请提供：

(A) 为什么当前的解决方案是这样的 (B) 如何重构代码，以便捕获单热的“拿或不拿”向量，表示给定物品是否放入背包。

谢谢！

Answer 1

(A) Why the current solution is behaving this way

self.array 是所有递归路径共享的实例属性。在一条或另一条路径上，每个项目都被采用，因此一个被附加到列表中。
option_A = val[index]... 获取一个项目但不将其添加到列表中。
option_B = self..... 跳过一个项目但不在列表中附加零。
if option_A > option_B: 进行此比较时，您丢失了进行的信息 - 分支中 taken/discarded 的项目；
- 在套件中，无论有多少项目产生这些值，您只需附加一个 1 或 0。
- 1 和 0 表示 分支 A (1) 还是 分支 B (0 ) 在函数的当前实例中成功。

(B) How the code can be restructured such that a one-hot "take or don't take" vector can be captured, representing whether a given item goes in the knapsack or not.

很高兴通过分析知道你在运行之后采取了什么，我怀疑这就是你试图用[=14=做的事情].您表达了对 OOP 的兴趣：不是使用列表中 select 数字的索引来跟踪数字列表，而是让对象来表示项目与这些项目一起工作。将对象保存在容器中，并使用容器的功能向其中添加或删除 items/objects。在选择一个容器之前考虑您将如何使用容器。

不要将函数放在 class.
更改函数的签名以接受
- 可用重量，
- 要考虑的项目的容器，
- 一个容器持有当前袋子中的物品（当前袋子）。
对具有价值和重量属性的项目使用 collections.namedtuple 或 class。
- ```
Item = collections.namedtuple('Item',['wt','val'])
```
拿走一件物品后，将其添加到当前袋子。
递归时
- 如果沿着走路径，将调用中的 return 值添加到 当前的 sack
- 从要考虑的项目列表参数中删除刚刚考虑的项目。
- 如果采取从可用重量参数中减去物品的重量
比较两个分支时，您需要将每个项目的值相加当前麻袋。
- return价值最高的麻袋
仔细考虑基本情况

像这样制作要考虑的项目。

import collections
Item = collections.namedtuple('Item',['wt','val'])
items = [Item(wght,value) for wght,value in zip(wt,val)]

像这样累加值。

value = sum(item.val for item in current_sack)
# or
import operator
val = operator.itemgetter('val')
wt = operator.itemgetter('wt')
value = sum(map(val,current_sack)

您的解决方案通过 调试打印 增强了好奇心。

class Solution:
    def __init__(self):
        self.array = []
        self.other_array = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    
    def knapSack(self,W, wt, val, n,j=0):
        index = n-1 
        deep = f'''{' '*j*3}'''
        print(f'{deep}level {j}')
        print(f'{deep}{W} available: considering {wt[index]},{val[index]}, {n})')
        # minor change here but has no affect on the outcome0
        #if n == 0 or W == 0 :
        if n == 0:
            print(f'{deep}Base case found')
            return 0
        print(f'''{deep}{wt[index]} > {W} --> {wt[index] > W}''')
        if (wt[index] > W):
            print(f'{deep}too heavy')
            self.array.append(0)
            self.other_array[index] = 0
            choice = self.knapSack(W, wt, val, index,j+1) 

        else:
            print(f'{deep}Going down the option A hole')
            option_A = val[index] + self.knapSack( W-wt[index], wt, val, index,j+1)
            print(f'{deep}Going down the option B hole')
            option_B = self.knapSack(W, wt, val, index,j+1)
            print(f'{deep}option A:{option_A} option B:{option_B}')
            if option_A > option_B:
                print(f'{deep}option A wins')
                self.array.append(1)
                self.other_array[index] = 1
                choice = option_A
            else:             
                print(f'{deep}option B wins')
                self.array.append(0)
                self.other_array[index] = 0
                choice = option_B

        print(f'{deep}level {j} Returning value={choice}')
        print(f'{deep}---------------------------------------------')
        return choice

将缓存数组添加到递归背包解决方案？

Adding a cache array to recursive knapsack solution?

python

recursion

knapsack-problem

dynamic-programming