0

所以我有一个问题的典型递归实现，需要一个 1-0 类似背包问题的解决方案。这是主要功能的代码：

def knapsack(items,sizeLimit):
    P = {}

    def recurse(nItems,lim):
        if not P.has_key((nItems,lim)):
            if nItems == 0:
                P[nItems,lim] = 0
            elif itemSize(items[nItems-1]) > lim:
                P[nItems,lim] = recurse(nItems-1,lim)
            else:
                P[nItems,lim] = max(recurse(nItems-1,lim),
                    recurse(nItems-1,lim-itemSize(items[nItems-1])) +
                    itemValue(items[nItems-1]))
        return P[nItems,lim]

    return recurse(len(items),sizeLimit)

问题是我有数以百万计的数据，而且似乎这种方法会计算每个条目，导致明显的内存和速度问题。我可以使用某种动态编程/记忆技术来进一步优化此实现吗？

4

1 回答 1

0

扩展问题时，您似乎遇到了问题，请查看特定此文件中的此目录示例

以下内容来自给定的网址：

如果您的背包问题由 (1,2)、(1.5,1)、(0.5,3) 定义的三个项目（重量、价值）和一个最大重量为 2 的袋子组成，您可以通过以下方式轻松解决： ：

sage: from sage.numerical.knapsack import knapsack
sage: knapsack( [(1,2), (1.5,1), (0.5,3)], max=2)
[5.0, [(1, 2), (0.500000000000000, 3)]]

超增序列

我们可以测试一个序列是否超增::

sage: from sage.numerical.knapsack import Superincreasing
sage: L = [1, 2, 5, 21, 69, 189, 376, 919]
sage: seq = Superincreasing(L)
sage: seq
Super-increasing sequence of length 8
sage: seq.is_superincreasing()
True
sage: Superincreasing().is_superincreasing([1,3,5,7])
False

解决超增序列和目标和的子集和问题::

sage: L = [1, 2, 5, 21, 69, 189, 376, 919]
sage: Superincreasing(L).subset_sum(98)
[69, 21, 5, 2, 1]

"""

此外，还有一个来自Number Jack的文件，要对此进行测试，您必须导入所有必要的文件。

于 2012-12-23T19:22:32.993 回答