背包问题-如何减少内存使用

Question

您有 𝑛 件物品。每个物体都有一个重量，编号为𝑖的物体的重量等于𝑥_𝑖。您需要将它们放入可容纳不超过 𝑆g 的背包中。同时，您希望背包中所有物品的总重量尽可能大，同时它（总重量）为奇数。如果不能输入奇数权重，则输入 0。

输入数据 第一行给出可用项目的数量 0≤𝑛≤25。第二行列出了 𝑛 数字——物体的重量。物品重量不超过10^9。第三行包含数字0≤𝑆≤10^18，这是对放入背包中的物品总重量的限制。

输出 第一行打印可以放入背包的物品的最大奇数总重量。

**我的解决方案**

import sys

def max_odd_weight(n, weights, S):
    possible_sums = {0}  
  
    for weight in weights:
        current_sums = set(possible_sums)  
        for w in current_sums:
            new_sum = w + weight
            if new_sum <= S:
                possible_sums.add(new_sum)  

    max_odd_weight = 0
    for w in possible_sums:
        if w % 2 != 0 and w > max_odd_weight:
            max_odd_weight = w

    return max_odd_weight

n = int(sys.stdin.readline())
weights = list(map(int, sys.stdin.readline().split()))
S = int(sys.stdin.readline())

result = max_odd_weight(n, weights, S)
sys.stdout.write(str(result))

它确实很快，但我在通过测试时遇到问题（全部正确，但超出了内存限制）。测试数据被隐藏。 如何进一步减少内存使用？

测试时间限制 - 3秒 每个测试的内存限制 - 256 MB 输入-标准输入 输出 - 标准输出

使用 SYS 有帮助，但效果不大

Answer 1

问题的约束意味着可能有超过 3400 万个可能的总和，如果您使用 0-1 背包的标准动态规划解决方案，这些总和将无法容纳在内存中。

但是项目数量有限，所以我建议使用递归回溯，如下所示：

import sys

def max_weight(weights, start, limit, odd):
    result = None if odd else 0
    for i in range(start, len(weights)):
        w = weights[i]
        if w <= limit:
            test = max_weight(weights, i+1, limit-w, not odd)
            if test != None:
                test += w
                if (result == None or test > result):
                    result = test
    return result

n = int(sys.stdin.readline())
weights = list(map(int, sys.stdin.readline().split()))
S = int(sys.stdin.readline())

result = max_weight(weights, 0, S, True)
sys.stdout.write(str(result))