Python 递归记忆

Question

我有以下作业：给定一个包含 n 个整数的列表，列表中的每个整数都是唯一的并且大于 0。我还得到一个数字 K - 这是一个大于 0 的整数。 不允许任何类型的列表切片

我需要检查是否存在总和为 K 的子集。例如：对于列表 [1,4,8] 和 k=5，我 return 正确，因为我们有子集 {1,4}.

现在我需要使用递归来实现它：所以我做了，但是我需要实现记忆：

我想知道这些函数的代码有什么区别：我的意思是，两者似乎都实现了记忆，但是第二个应该工作得更好，但事实并非如此。非常感谢您的帮助:)

def subsetsum_mem(L, k):
    '''
    fill-in your code below here according to the instructions
    '''
    sum_dict={}
    return s_rec_mem(L,0,k,sum_dict)



def s_rec_mem(L, i, k, d):
    '''
    fill-in your code below here according to the instructions
    '''
    if(k==0):
        return True
    elif(k<0 or i==len(L)):
        return False
    else:
        if k not in d:
            res_k=s_rec_mem(L,i+1,k-L[i],d) or s_rec_mem(L,i+1,k,d)
            d[k]=res_k
            return res_k


def subsetsum_mem2(L, k):
    '''
    fill-in your code below here according to the instructions
    '''
    sum_dict={}
    return s_rec_mem2(L,0,k,sum_dict)


def s_rec_mem2(L, i, k, d):
    '''
    fill-in your code below here according to the instructions
    '''
    if(k==0):
        return True
    elif(k<0 or i==len(L)):
        return False
    else:
        if k not in d:
            res_k=s_rec_mem2(L,i+1,k-L[i],d) or s_rec_mem2(L,i+1,k,d)
            d[k]=res_k
            return res_k
        else:
            return d[k]

Answer 1

你的记忆有两个问题。

首先，您仅使用 k 作为缓存键。但是该函数对 i 的不同值执行不同的操作，并且您忽略了缓存中的 i，因此您将最终 returning 来自 [=14] 的值=] 对于 L, 1, 1, d.

其次，只在s_rec_mem，你永远不会returnd[k]；如果它存在，你就会从最后掉下来 return None （这是错误的）。

因此，第二个确实更接近于工作——但实际上仍然没有工作。

你可以这样修复它：

def s_rec_mem2(L, i, k, d):
    '''
    fill-in your code below here according to the instructions
    '''
    if(k==0):
        return True
    elif(k<0 or i==len(L)):
        return False
    else:
        if (i, k) not in d:
            res_k=s_rec_mem2(L,i+1,k-L[i],d) or s_rec_mem2(L,i+1,k,d)
            d[i, k]=res_k
            return res_k
        else:
            return d[i, k]

… 或仅使用 lru_cache，通过向下传递 tuple(L) 而不是 L（因为元组与列表不同，可以作为键散列，而您的递归函数不会不关心它得到什么样的序列），或者通过使它成为一个本地函数，通过闭包看到 L 而不是将它作为参数传递。

最后，快速浏览一下您的代码：

看起来你只会在每组参数上最多评估 s_rec_mem 两次（假设你正确地缓存在 i, k 而不仅仅是 k），这意味着记忆最多只能提供 2 倍的恒定加速。要获得更多，您需要重新考虑缓存或算法。
您仅在每个单独的顶级运行内进行记忆，但是在 tuple(L), i, k 上切换到 lru_cache 意味着您正在对所有运行进行记忆，直到你重新启动程序（或 REPL 会话）——所以第一个测试可能需要很长时间，但是相同 L（即使有不同的 k）的后续运行s 可以受益于以前的缓存。
您似乎在尝试解决子集和问题的一个小变体。在一般情况下，该问题可证明是 NP 完全问题，这意味着保证需要指数时间。而且您的变体似乎比标准问题更难，而不是更容易。如果是这样，不仅您的常数因子加速不会有太大好处，而且您确实没有什么可以做得更好。在现实生活中，解决等价问题的人通常使用优化（例如，通过动态规划）或在任意指定限制内的近似，这两种方法在大多数情况下都允许多项式（或至少伪多项式）解决方案，但可以'解决所有案件。或者，对于某些输入子类，您可以在多项式时间内解决问题，如果幸运的话，您可以证明您的输入属于这些子类之一。如果我猜对了你在做什么，并且你想追求这三个选项中的任何一个，你需要做一些研究。（也许 Wikipedia 已经足够好了，或者也许这里或 compsci 或 math SE 网站上有很好的答案可以帮助您入门。）

Python 递归记忆

Python recursion memoization

python

recursion

memoization