您有 𝑛 件物品。每个物体都有一个重量,编号为𝑖的物体的重量等于𝑥_𝑖。您需要将它们放入可容纳不超过 𝑆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 兆字节输入 - 标准输入输出 - 标准输出
使用 SYS 有帮助,但效果不大