0-1 Knapsack Problem

#1

Please help me in building approach for this problem,

#2

In case of 0 1 knapsack u have 2 options: 1. i should take this element 2. i will not take this element. After any of the above two option the remaining items in bag will be n-1.(assuming that initial we have n items)

The brute force way is to consider any one of the ways at every step and calculate by recursion.
But since there are overlapping subproblems we will use dp.

#3

i have implemented Recursive approach, but im unable to think of the db based approach

#4

have u understood the top down dp approach??

#5

ik what is top down dp approach,but don’t know how to implement in this question and what to store

#6

see the variable which are changing in ur recursion. these variables need to be stored.

#7
#8

im getting segmentation fault :confused:

#9

It is because u are running loop from i=0. at the start when i=0 then wt[i-1] = wt[-1] not possible.

#10

but for i equal to zero i have marked the condition in line 31, and when the value of i will be greater than 0 then only wt of i minus 1 will be processed