将缓存数组添加到递归背包解决方案？ [英] Adding a cache array to recursive knapsack solution?
问题描述
我熟悉背包问题的幼稚递归解决方案。但是，在给定其重量限制的情况下，此解决方案只会吐出可存储在背包中的最大值。我想做的是添加某种形式的元数据缓存（即使用一次性数组 [0,1,1] ）。
I'm familiar with the naive recursive solution to the knapsack problem. However, this solution simply spits out the max value that can be stored in the knapsack given its weight constraints. What I'd like to do is add some form of metadata cache (namely which items have/not been selected, using a "one-hot" array [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 返回 [1,1,1,1,1,1] ，这告诉了我一些事情。 （1），即使问题集中只有三个项目，对于每个项目，knapSack方法也被调用了两次；（2）这是因为每个项目都流过 else 语句，因此分别为每个项目计算 option_A 和 option_B （解释为什么数组长度为6不是3。）
As you can see, s.array returns [1,1,1,1,1,1] and this tells me a few things. (1), even though there are only three items in the problem set, the knapSack method has been called twice for each item and (2) this is because every item flows through the else statement in the method, so option_A and option_B are each computed for each item (explaining why the array length is 6 not 3.)
我很困惑为什么在每个递归循环中都附加了1。最佳解决方案中不会选择索引为0的项目。要回答这个问题，请提供：
I'm confused as to why 1 has been appended in every recursive loop. The item at index 0 would is not selected in the optimal solution. To answer this question, please provide:
（A）为什么当前的解决方案采用这种方式
（B）如何重构代码以使一键式 ;接受或不接受向量可以被捕获，代表给定的项目是否放入背包。
(A) Why the current solution is behaving this way (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.
谢谢！
推荐答案
（A）为什么当前解决方案采用这种方式
(A) Why the current solution is behaving this way
-
self.array是所有递归路径共享的实例属性。在一条路径或另一条路径上，每一项都被采用，因此一项附加到列表中。 -
option_A = val [index] ...接受一项，但不将其追加到列表中。 -
option_B = self .....跳过一个 -
如果option_A> option_B：进行比较时，您丢失了 所做的信息-分支中已取出/丢弃的物品；
- 在套件中，您只需附加一个或零即可，无论多少个制成这些值。
- 1和0代表分支A （
1）还是分支B （0）在该函数的当前实例中是成功的。 self.arrayis an instance attribute that is shared by all recursion paths. On one path or another each item is taken and so a one is appended to the list.option_A = val[index]...takes an item but doesn't append a one to the list.option_B = self.....skips an item but doesn't append a zero to the list.if option_A > option_B:When you make this comparison you have lost the information that made it - the items that were taken/discarded in the branch;- in the suites you just append a one or a zero regardless of how many items made those values.
- The ones and zeroes then represent whether branch A (
1) or branch B (0) was successful in the current instance of the function. - 不要将函数放在类中。
- 更改函数的签名以接受
- 可用重量
- 要考虑的项目容器，
- 一个容器保存当前麻袋中的物品（当前麻袋）。
- Don't put the function in a class.
- Change the function's signature to accept
- available weight,
- a container of items to be considered,
- a container holding the items currently in the sack (the current sack).
Item = collections.namedtuple('Item',['wt','val'])
- 如果在 take 路径将调用的返回值添加到当前麻袋
- 删除正好的项目从要考虑的项目列表中考虑。
- 如果采用，则从可用的权重参数中减去项目的权重
- if going down the take path add the return value from the call to the current sack
- remove the item that was just considered from the list of items to be considered argument.
- if taken subtract the item's weight from the available weight argument
- 退回价值最高的麻袋
使项目成为这样。
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)
< hr />
您的解决方案通过调试打印来增强您的好奇心。
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这篇关于将缓存数组添加到递归背包解决方案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
（B）如何重新构造代码，以便一次性使用接受或不接受。向量可以被捕获，代表给定项目是否放入背包。
(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.
很高兴知道您是什么人经过分析后，我怀疑这是您尝试使用
self.array进行的操作。您表达了对OOP的兴趣：与其使用索引从列表中选择数字来跟踪数字列表，不如使对象表示与之配合使用的对象。将对象保留在容器中，并使用容器的功能从中添加或删除项目/对象。在选择容器之前，请考虑一下如何使用容器。It would be nice to know what you have taken after running through the analysis, I suspect that is what you are trying to do with
self.array. You expressed an interest in OOP: instead of keeping track with lists of numbers using indices to select numbers from the lists, make objects to represent the items work with those. Keep the objects in containers and use the functionality of the container to add or remove items/objects from it. Consider how you are going to use a container before choosing one.
