Knapsack 0/1 problem:Given N items where each item has some weight and profit associated with it and also givena bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put theitems into the bag such that the sum of profits associated with them is the maximumpossible.Given the problem is solved using a dynamic programming approach and the matrix derivedis given below, answer the below set of questions by analyzing the DP matrix.weights = [2, 3, 4, 5], profits = [1, 2, 5, 6], Capacity W = 8Capacity23Profits weights|01251614|->5100O101 2 3 40 O0 1 10 10 1O1012 2252O155013566O1361800378710 101377118 From the Knapsack DP matrix given above,what is the maximum profit earned whentheCapacity = 4weights available = [2,3,4]5182

All you need to do is understand the DP table.The table is such that, at any weight W, you can check the maximum profits, with that number of weights.This is example to make you understand the working, In Step 2, I have solved the answer.Now, suppose I want to check the maximum profits when the bag has capacity 5 and it has weights 2 and 3.So, I will look at row 3 weight row, and column 5, that is, the value of matrix at row 3 (weight) and column 5 (capacity), that is, 3.I have circled it here.Now, I think you must have known how it works, As asked in question we have weights, [2,3,4] and Capacity 4, so, we will look in the row with the maximum weight above which all others are taken care of, that is, 4, as maximum weight for 2 and 3 is already added in 4.For columns with capacity 4.I have marked it,so, the answer is: 5.So, first option is correct option, that is, 5.The correct answer is 5, as for capacity 4, and weights [2,3,4], We will look the matrix with row value 4 (max weight), and col values 4 (capacity), that is, 5.So, the answer is 5.

Answered: From the Knapsack DP matrix given…

Engineering

Data Structures and Algorithms

From the Knapsack DP matrix given above, what is the maximum profit earned when the Capacity = 4 weights available = [2,3,4]