python - 使用内存的递归算法

Question

我的问题如下:我有一个任务列表，每个任务都需要特定的时间并授予特定数量的点数，以及执行它们的时间“k”:

例如:missions = [(14,3),(54,5),(5,4)] 和 time = 15

在这个例子中，我有 3 个任务，第一个任务给了我 14 分，耗时 3 分钟。我总共有 15 分钟。每个任务都是一个元组，第一个值是该任务的点数，第二个值是执行该任务所需的分钟数。

我必须使用内存递归地找到在给定的任务列表和给定的时间内我可以获得的最大点数。

我正在尝试实现一个名为 choose(missions,time) 的函数，该函数将递归运行并使用函数 choose_mem(missions,time,mem,k) 来实现我的目标。函数 choose_mem 应该得到“k”，这是可供选择的任务数，mem 是一个空字典，mem，它将包含之前已经解决的所有问题。

这是我到目前为止得到的，我需要帮助来实现上面的要求，我的意思是字典的使用(目前就在那里并且一直是空的)，还有我的 choose_mem 函数输入是 i,j,missions,d 和它应该是 choose_mem(missions, time, mem, k)，其中 mem = d，k 是可供选择的任务数。

如果有人可以帮助我调整我的代码，将不胜感激。

mem = {}

def choose(missions, time):
    j = time
    result = []
    for i in range(len(missions), 0, -1):
        if choose_mem(missions, j, mem, i) != choose_mem(missions, j, mem, i-1):
            j -= missions[i - 1][1]
    return choose_mem(missions, time, mem, len(missions)) 

def choose_mem(missions, time, mem, k): 
    if k == 0: return 0
    points, a = missions[k - 1]
    if a > time:
        return choose_mem(missions, time, mem, k-1) 
    else:
        return max(choose_mem(missions, time, mem, k-1),
                   choose_mem(missions, time-a, mem, k-1) + points)

Answer 1

这有点含糊，但您的问题大致可以转化为一个非常著名的 NP 完全问题，即背包问题。

你可以在维基百科上阅读更多关于它的信息，如果你用时间代替重量，你就有问题了。

动态编程是解决该问题的常用方法，如您在此处所见: http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

对于实际问题，记忆化或多或少等同于动态规划，所以不要被花哨的名字所蒙蔽。

基本概念是您使用额外的数据结构来存储您已经解决的部分问题。由于您正在实现的解决方案是递归的，因此许多子问题会重叠，而记忆化允许您对每个子问题只计算一次。

所以，困难的部分是你要考虑你的问题，你需要在字典中存储什么，这样当你用你已经计算出的值调用 choose_mem 时，你只需检索他们从字典中，而不是做另一个递归调用。

如果您想检查通用 0-1 背包问题的实现(您的情况，因为您不能部分添加项目)，那么在我看来这是一个很好的资源:

https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p

解释的很好，代码也足够可读。如果您了解矩阵存储成本的用法，那么您的问题就会迎刃而解。