CODEWITHSUNDEEP
pythonalgorithmoutput
MD-4
MD-4

Reputation: 311

Knapsack algorithm dynamic programming .(incorrect output) here is what I have so far

I wrote this code for dynamic programming implementation of the knapsack problem.

#B = maximum weight
#n = number of items
#p = list of weights
#a = list of values

#p[i] = weight with value a[i]



   def maximum_attractiveness(n, B, p, a):
     f = [i for i in range(n+1)]
     m = [f for i in range(B+1)]
     m[0] = [0 for i in range(len(m[0]))]
     for i in m:
      i[0] = 0
     print(m)
     for j in range(n):
      for w in range(B):
       if (p[j]) > (w):
        m[w][j] = m[w][j-1]
       else:
        m[w][j] = max(m[w][j-1],m[w-p[j]][j-1]+a[j])
    return m[B][n]

I get an incorrect output for this algorithm. where did I go wrong?

Upvotes: 1

Views: 1772

Answers (1)

Niklas B.
Niklas B.

Reputation: 95308

f = [i for i in range(n+1)]
m = [f for i in range(B+1)]

This uses the same array f for every position m, so for example if you change m[1][k], you also change m[i][k] for every i. You probably meant to do

m = [[i for i in range(n+1)] for i in range(B+1)]

There might be some other bugs I think, so maybe you should print out the intermediate arrays at some points to check out where the results are not what you'd expect them to be.

UPDATE:

  • Your initialization seems strange to me. I think it should be just m = [[0]*n for i in range(B+1)] because you need a matrix of zeroes.
  • it should be for w in range(B+1)
  • you should not return m[B][n], but max(m[j][n] for j in range(B+1)).

My attempt, which avoids the the matrix altogether and only uses a single array:

m = [0]*(B+1)
for j in range(n):
    for w in range(B,p[j]-1,-1):
        m[w] = max(m[w], m[w-p[j]] + a[j])
return max(m)

Upvotes: 3

Related Questions