NIELIT 2017 July Scientist B (IT) - Section B: 60

Question

$0/1$-Knapsack is a well known problem where, it is desired to get the maximum total profit by placing $n$ items (each item is having some weight and associated profit) into a knapsack of capacity $W$. The table given below shows the weights and associated profits for $5$ items, where one unit of each item is available to you. It is also given that the knapsack capacity $W$ is $8$. If the given $0/1$ knapsack problem is solved using Dynamic Programming, which one of the following will be maximum earned profit by placing the items into the knapsack of capacity $8$. $$\begin{array}{|c|c|c|}\hline \textbf{Item#}&\textbf{Weight}&\textbf{Associated Profit} \\\hline \text{1}&\text{1}&\text{3}\\\hline\text{2}&\text{2}&\text{5}\\\hline\text{3}&\text{4}&\text{9}\\\hline\text{4}&\text{5}&\text{11}\\\hline\text{5}&\text{8}&\text{18} \\\hline\end{array}$$

• A. $19$
• B. $18$
• C. $17$
• D. $20$

Comments

Option A:19 max profit we can earn here.

Answer 1

19 is correct.

We can get maximum profit by including item 1,2,4.

Answer 2

option A) 19 , as it is a 0/1 knapsack we can include item 1,2 and 5 to get maximum profit of 3+5+11=19