python - 以下背包填充算法的实现有什么问题？

Question

Edit2: 现在测试失败({64, 1, 36, 81}, 82)
Edit1:现在已更新以解决由于 delta > max(items)
引起的问题Edit0:现在已更新以修复由于振荡增量问题导致的无限递归。

---

在this算法视频(2:52 左右)Skiena 教授指定背包问题如下...

背包问题:给定一组整数 S = {s1, s2,..., sN} 并给定目标数 T 找到 S 的一个子集，该子集恰好相加 到 T。

然后他继续说，这是没有已知有效解决方案的问题之一!

但我还是尝试了，这是我尝试的解决方案(它似乎适用于我尝试过的数字)...

from itertools import accumulate

#items   - All available items
#target  - The size of the knapsack
#returns - A subset of {items} whose sum adds upto target
#          if possible else returns None
def KnapsackItems(items, target):
    s = sum(items)
    if s < target:
        return None
    delta = s - target

    if delta == 0:
        return items

    if delta in items:
        result = items - {delta}
        return result

    if delta > max(items):
        sortedItems = list(sorted(items))
        deltas = list(map(lambda x: x - target, accumulate(sortedItems)))
        ul = [i for i,d in zip(sortedItems, deltas) if d <= i]
        return KnapsackItems(set(ul), target)
    else:
        U = {i for i in items if i < delta}

    V = KnapsackItems(U, delta)
    if V:
        result = items - V
        return result
    return None

这是测试工具...

def test(items, target):
    print("Items:", items)
    print("Target:", target)

    result = KnapsackItems(items, target)

    if result and not sum(result) == target:
        print("Result:", result)
        print("FAIL: sum of returned set does not match target ({})".format(target))
    elif result:
        print("Result:", result)
        print("Success (sum of returned set:{})".format(sum(result)))
    else:
        print("No solution could be found")

视频中的示例...

test({1,2,5,9,10}, 22)
test({1,2,5,9,10}, 23) #No solution expected
test({1,2,3,4,5}, 11)
test({1,2}, 2)
test({4,3,2}, 5)
test({1, 3, 4, 7, 9}, 13)
test({6,7,8,3,14,5,15,2,4}, 29)
test({1,2,3,4,5,6,7},14)
test({64, 1, 36, 81}, 82)

结果...

Items: {9, 10, 2, 5, 1}
Target: 22
Result: {9, 10, 2, 1}
Success (sum of returned set:22)

Items: {9, 10, 2, 5, 1}
Target: 23
No solution could be found

Items: {1, 2, 3, 4, 5}
Target: 11
Result: {1, 2, 3, 5}
Success (sum of returned set:11)

Items: {1, 2}
Target: 2
Result: {2}
Success (sum of returned set:2)

Items: {2, 3, 4}
Target: 5
Result: {2, 3}
Success (sum of returned set:5)

Items: {9, 3, 4, 1, 7}
Target: 13
Result: {9, 4}
Success (sum of returned set:13)

Items: {2, 3, 4, 5, 6, 7, 8, 14, 15}
Target: 29
Result: {14, 15}
Success (sum of returned set:29)

Items: {1, 2, 3, 4, 5, 6, 7}
Target: 14
Result: {2, 5, 7}
Success (sum of returned set:14)

Items: {64, 81, 36, 1}
Target: 82
No solution could be found

所以现在我想问题是我对背包问题的解决方案有什么问题？对于非常大的数字集，它是否效率低下且无法使用？如果这里不适合此类问题，也请告诉我。

Answer 1

当 max(items) < target < sum - max(items) (我不懂 Python)然后 delta永远超过max(items)并且在递归检查之前不会删除任何项目，并且算法永远不会终止。

编辑版本:

它现在在 max(items) 时失败不能是解决方案的一部分(例如 max(items) > target )和 max(items) < delta .示例:{2, 3, 4, 6}, 5 .第一次迭代后，它变为 {2, 3, 4}, 10 ，返回 None ，导致顶层调用返回 None ，这是不正确的。