2

我的问题如下：我有一个任务列表，每个任务都需要特定的时间并授予特定数量的积分，以及执行它们的时间“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)
4

1 回答 1

4

这有点含糊，但是您的问题大致翻译为一个非常著名的 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

解释得很好，代码也足够可读。如果您了解使用矩阵来存储成本，那么您的问题就会为您解决。

于 2013-05-10T09:29:03.160 回答