Doubt where max value is being assigned to dp[i][w]

#1

in the line dp[i][w]=max(dp[i][w], ar[i].val+dp[i-1][w-ar[i].wt] cant we use dp[i][w]=max(dp[i][w], ar[i].val+dp[i][w-ar[i].wt]
and why max_element is returned in the last an not simply dp[n][w]

#2

hello @simi_1188

a) no u cannot use i in place of i-1 because count of each item is 1 so if we have already included some item , then we cant include it again. and that is the basic difference between 0-1 knapsack and o-n knapsack.

b) yeah dp[n][w] should work

#3

https://ide.codingblocks.com/s/258960

#4

my code is giving some error

#5

image
declare ur vector like this

#6

2
78
94 85
61 18
ans is coming wrong for this test case ans should be 94

#7

2 78 94 85 61 18 ans is coming wrong for this test case ans should be 94

#8

check ur corrected code->

intiialised dp array with 0.

start i from 1

#9

it is still giving wrong ans for many test cases

#10

where u r submitting?
if possible pls share link

#11

geeks for geekshttps://practice.geeksforgeeks.org/problems/0-1-knapsack-problem/0

#12

u have to run ur code for t test cases (check their input format)

here is ur corrected code->

#13

yes now its running but can u explain what was wrong with my previous i initialised dp array 0 when n was 1 and then ran both the loops

#14

… . … … … …

#15

no im asking in this one
https://ide.codingblocks.com/s/258960?_ga=2.188109288.117621104.1592220342-1995481792.1587055833

#16

image
u should initialise dp[1][j]=a1[i].val for j >=a1[1].val

and intialise ur dp array with 0 ,to avoid any garbage value

1 Like
#17

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.