Ошибка памяти Traceback Python

Question

Я пишу в python, и это то, что я хочу делать: Первая строка ввода содержит количество пластин n (1≤n≤1000). Каждая из следующих n строк содержит одно положительное целое число, меньшее или равное 1000, обозначая вес каждой пластины. Выведите одно целое число, объединенный вес, ближайший к 1000. Если существует два таких числа, которые одинаково близки к 1000 (например, 998 и 1002), выберите большую (в этом случае 1002).

Мой код выглядит следующим образом righet сейчас:

from itertools import permutations, chain 
N=int(input()) 
s=0 
vikter=[] 
while (N>s): 
    vikt=int(input()) 
    vikter.append(vikt) 
    s=s+1 
c = chain(*(list(permutations(vikter, i)) for i in range(1, len(vikter) + 1))) 
result = min(c, key = lambda x: (abs(sum(x) - 1000), -sum(x))) 
print(result) 

Но этот код дает мне эту ошибку памяти:

Traceback (most recent call last): 
File "C:\Users\Hanna\Documents\walrusweights.py", line 9, in <module> 
c = chain(*(list(permutations(vikter, i)) for i in range(1, len(vikter) + 1))); 
File "C:\Users\Hanna\Documents\walrusweights.py", line 9, in <genexpr> 
c = chain(*(list(permutations(vikter, i)) for i in range(1, len(vikter) + 1))); 
MemoryError 

, что я могу сделать, чтобы избежать этой ошибки?

Answer 1

Ваша проблема в том, что вы используете грубую силу там, где она неприменима. Вы пытаетесь сгенерировать все возможные перестановки списка, который имеет (в худшем случае) 1000 элементов. Количество перестановок, таких как список, равно 1000 !, которое слишком велико для обработки в течение жизни этого юниверса. Вместо этого вы можете посмотреть динамическое программирование или алгоритм Branch and Bound для реализации этой проблемы.