Witam,
mam problem z poniższym kodem ponieważ nie został zaakceptowany
przez
spoj z powodu błędu "limit czasu został przekroczony".
Proszę o pomoc w optymalizacji tego kodu lub w wyborze innego
szybszego algorytmu.

Zadanie znajduje się pod adresem http://pl.spoj.pl/problems/KC024


def a(sum,tab):


n=len(tab)
tmp=sum


for i in range(n):
if sum-int(tab[i])>=0:
sum=sum-int(tab[i])
if sum==0:
return 1


for j in range(i+1,n):
if sum-int(tab[j])>=0:


sum=sum-int(tab[j])
if sum==0:
return 1


sum=tmp


while 1:
try:
we = raw_input().split()
except EOFError: break
W=int(we[0])
tab=we[2:]


tab.sort(reverse=1)
if a(W,tab):
print "1"
else:print "0"

do góry

Na moje oko, twoj kod nie wyglada nawet na poprawny algorytm, bo
robisz to zbyt zachlannie. Jakie rozwiazanie jest poprawne i
efektywne, sadze ze wiem, ale nie bede zdradzal publicznie, zeby nie
psuc innym zabawy (mozesz mnie pytac na priv).

-Marcin Stefaniak

do góry