retagged by
2,619 views
1 votes
1 votes

$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}$$

  1. $19$
  2. $18$
  3. $17$
  4. $20$
retagged by

2 Answers

1 votes
1 votes
19 is correct.

We can get maximum profit by including item 1,2,4.
0 votes
0 votes
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
Answer:

Related questions

2 votes
2 votes
2 answers
1
admin asked Mar 30, 2020
2,199 views
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } }$O(n)...
0 votes
0 votes
1 answer
2
admin asked Mar 30, 2020
9,911 views
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is$E$$2E$$V$$2V$
0 votes
0 votes
1 answer
4
admin asked Mar 30, 2020
2,047 views
A path in graph $G$, which contains every vertex of $G$ and only once?Euler circuitHamiltonian pathEuler PathHamiltonian Circuit