用动态规划解决一个类似背包的难题

Question

所以我有一个典型的递归实现问题，它需要一个类似于1-0背包问题的解决方案。下面是main函数的代码:

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)

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

Answer 1

似乎你在扩展问题时遇到了问题看看这个dir的例子，在这个文件

中

以下内容取自给定url:

如果你的背包问题由三个项目组成(重量，价值)由(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

求解超递增序列的子集和问题和目标sum::

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

" " "

还有一个来自Number Jack的，为了测试这个，你必须导入所有必要的文件