python - 使用内存的递归算法

我的问题如下：
我有一份任务清单，每个任务都需要特定的时间和点数，以及执行任务的时间“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)

最佳答案

这有点模糊，但是你的问题被粗略地转化为一个非常著名的NP完全问题，背包问题。
你可以在维基百科上多读一点，如果你用时间代替体重，你就有问题了。
动态编程是解决该问题的常见方法，如您所见：
http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming
对于实际问题，记忆或多或少相当于动态编程，所以不要让花哨的名字愚弄你。
基本概念是使用额外的数据结构来存储已经解决的部分问题。由于您正在实现的解决方案是递归的，许多子问题将重叠，并且memoization允许您只计算其中的每一个问题一次。
所以，困难的部分是你要考虑你的问题，你需要在字典中存储什么，这样当你用你已经计算过的值调用choose_mem时，你只需要从字典中检索它们，而不是做另一个递归调用。
如果您想检查一般0-1背包问题的实现（您的情况，因为您不能部分添加项），那么在我看来这是一个很好的资源：
https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p
它解释得很好，代码也足够可读。如果你了解矩阵存储成本的用法，那么你的问题就可以解决了。

Mem

python - 使用内存的递归算法