Part of the reason you're running out of memory is that you are allocating all of your items into memory twice. Once in the two lists weights and values, and once again in hash_table.
Looking at your program, I don't see a need for you to keep your weights and values allocated as you do. You iterate through them one at a time in your outer for loop. What I'd do is make use of a generator and wrap the file reading in a function:
def read_file():
with open('knapsack.txt') as fh:
# these value names are a bit more descriptive, and
# you can use a next() call on this generator
# to extract these values
WEIGHT, SIZE = map(int, next(fh).strip().split())
yield WEIGHT, SIZE
for line in fh:
yield map(int, line.strip().split())
This way you can do tuple unpacking in a for loop:
iterator = read_file()
# here's that next call I mentioned
WEIGHT, SIZE = next(iterator)
# iterate over the remaining values
for weight, value in iterator:
# do something
This will keep copies of your values from proliferating throughout the execution of your program when you really don't need them.
I'd also look into enumerate, since you need the index for part of your hash_table keys, but you also need the weight and value as well. This eliminate repeated lookups that slow down your code:
for i, (w, v) in enumerate(read_file(), start=1):
for x in range(WEIGHT + 1):
...
To show the effect:
# repeated index lookup
python -m timeit -s 'x = list(range(1, 10000))' 'for i in range(len(x)): a = x[i] + 2'
500 loops, best of 5: 792 usec per loop
# no repeated index lookup
python -m timeit -s 'x = list(range(1, 10000))' 'for i, j in enumerate(x): a = j + 2'
500 loops, best of 5: 536 usec per loop
It doesn't appear that you really need the leading 0 0 row on weights and columns, either, since you start the index at 1, skipping it. Avoiding the addition of lists here cuts down on overhead, and you can specify enumerate to start at a given value with the start kwarg as I've done above.
The goal here should be to iterate over a collection as little as possible, so a refactored version might look like:
def read_file():
with open('knapsack.txt') as fh:
# these value names are a bit more descriptive, and
# you can use a next() call on this generator
# to extract these values
WEIGHT, SIZE = map(int, next(fh).strip().split())
yield WEIGHT, SIZE
for line in fh:
yield map(int, line.strip().split())
iterator = read_file()
WEIGHT, SIZE = next(iterator)
hash_table = {(0, i): 0 for i in range(WEIGHT + 1)}
for i, (w, v) in enumerate(iterator, start=1):
for j in range(WEIGHT + 1):
if w > j:
hash_table[(i, j)] = hash_table[(i - 1, j)]
else:
hash_table[(i, j)] = max(
hash_table[(i - 1, j)],
hash_table[(i - 1, j - w)] + v
)
This doesn't avoid all of the memory issues, however. You are dealing with a relatively large file and housing that in a dictionary will lead to heavy memory usage. As noted in the Wikipedia article, the solution you have implemented will have a worst-case space complexity of O(nW), which for this file is approximately O(n * 2000000)
