0

I am getting Some Wierd output for the input of

1

3

4

1 2 3

4 5 1

I am getting output as 12

(HERE w is the capacity of the knapsack)

t=int(input())
while t:
   n=int(input())
   w=int(input())
   profits=tuple(map(int,input().split()))
   weights=tuple(map(int,input().split()))
   dp=[[0]*(w+1)]*(n+1)
   for i in range(n+1):
     for j in range(w+1):
        print()
        if i==0 or j==0:
            dp[i][j]=0
        elif j<weights[i-1]:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1],profits[i-1]+dp[i-1][j-weights[i-1]])
   print(dp[n][w])
   t-=1
Pari Raju
  • 25
  • 5

1 Answers1

0

There is a bug in line 7, dp=[[0]*(w+1)]*(n+1), notice that in this kind of initialization if you change one element you change all of the elements in this column. Here you can find a full answer about this bug, why is this happening and how to fix it. But at the end what you need to do is:

TL;DR

change dp=[[0]*(w+1)]*(n+1) to dp = [[0] * (w + 1) for _ in range(n + 1)].

Yonlif
  • 1,770
  • 1
  • 13
  • 31