Knapsack tle

[chaconnewu]

Dear all,

I'm using Dynamic Programming to solve the 0-1 KNAPSACK problem (spoj.pl/problems/KNAPSACK/) with python. But I only got TLE. I've try several test data, and when weight = 2000, number of items = 1000, it costs nearly 20s on my computer.

So I'm wondering if there's a better solution to solve this or is there something wrong with my code.

def fastMaxVal(w, v, i, aW, m):
    try:
        return m[(i, aW)]
    except KeyError:
        if i == 0:
            if w[i] < aW:
                m[(i, aW)] = v[i]
                return v[i]
            else:
                m[(i, aW)] = 0
                return 0
        without_i = fastMaxVal(w, v, i-1, aW, m)
        if w[i] > aW:
            m[(i, aW)] = without_i
            return without_i
        else:
            with_i = v[i] + fastMaxVal(w, v, i-1, aW-w[i], m)
        res = max(with_i, without_i)
        m[(i, aW)] = res
    return res
str = input()
tmp = str.split()
capacity = int(tmp[0])
number = int(tmp[1])
weightArray = []
valueArray = []
m = {}
for i in range(number):
    inputLine = input()
    tmp = inputLine.split()
    weightArray.append(int(tmp[0]))
    valueArray.append(int(tmp[1]))
print(fastMaxVal(weightArray, valueArray, len(weightArray) - 1, capacity, m))

Thank you guys in advance!