CODEWITHSUNDEEP
pythonalgorithmdynamic-programmingknapsack-problem
LiverToll92
LiverToll92

Reputation: 97

Knapsack problem(optimized doesn't work correctly)

I am working on the Python code in order to solve Knapsack problem.

Here is my code:

import time
start_time = time.time()
#reading the data:
values = []
weights = []
test = []
with open("test.txt") as file:

  W, size = map(int, next(file).strip().split())
  for line in file:
    value, weight = map(int, line.strip().split())
    values.append(int(value))
    weights.append(int(weight))

weights = [0] + weights
values = [0] + values

#Knapsack Algorithm:


hash_table = {}
for x in range(0,W +1):
  hash_table[(0,x)] = 0

for i in range(1,size + 1):
  for x in range(0,W +1):
    if weights[i] > x:
      hash_table[(i,x)] = hash_table[i - 1,x]
    else:
      hash_table[(i,x)] = max(hash_table[i - 1,x],hash_table[i - 1,x - weights[i]] + values[i])

print("--- %s seconds ---" % (time.time() - start_time))

This code works correctly, but on a big files my programm crashes due to RAM issues.

So I have decided to change the followng part:

for i in range(1,size + 1):
  for x in range(0,W +1):
    if weights[i] > x:
      hash_table[(1,x)] = hash_table[0,x]
      #hash_table[(0,x)] = hash_table[1,x]
    else:
      hash_table[(1,x)] = max(hash_table[0,x],hash_table[0,x - weights[i]] + values[i])
      hash_table[(0,x)] = hash_table[(1,x)]

As you can see instead of using n rows i am using only two(copying the second row into the first one in order to recreate the following line of code hash_table[(i,x)] = hash_table[i - 1,x]), which should solve issues with RAM.

But unfortunately it gives me a wrong result.

I have used the following test case:

190 6

50 56

50 59

64 80

46 64

50 75

5 17

Should get a total value of 150 and total weight of 190 using 3 items:

item with value 50 and weight 75,

item with value 50 and weight 59,

item with value 50 and weight 56,

More test cases: https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html

Upvotes: 1

Views: 195

Answers (1)

mpaepper
mpaepper

Reputation: 4022

The problem here is that you need to reset all the values in the iteration over i, but also need the x index, so to do so, you could use another loop:

for i in range(1,size + 1):
  for x in range(0,W +1):
    if weights[i] > x:
      hash_table[(1,x)] = hash_table[0,x]
    else:
      hash_table[(1,x)] = max(hash_table[0,x],hash_table[0,x - weights[i]] + values[i])
  for x in range(0, W+1): # Make sure to reset after working on item i
    hash_table[(0,x)] = hash_table[(1,x)]

Upvotes: 1

Related Questions