edited by
303 views
0 votes
0 votes
Consider the following instance of the knapsack problem :

$\begin{array}{|c|c|c|c|c|c|} \hline \text{Item} & a & b & c & d & e \\ \hline \text{Benefit} & 15 & 12 & 9 & 16 & 17 \\ \hline \text{Weight} & 2 & 5 & 3 & 4 & 6 \\ \hline \end{array}$

Maximum weight of knapsack is $12$. For the above weights and benefits of items, if we need an optimal solution of fractional knapsack problem, the value of maximum benefit will be ______.
edited by

1 Answer

Best answer
1 votes
1 votes
Item                                  a       b        c       d        e

profit per unit weight(p/w)   7.5    2.4     3       4        2.8

Highest p/w is 7.5 so take whole of 'a' . So knapsack capacity left = 12-2=10

Next highest is 4 so take whole of 'd'. Knapsack capacity left = 10-4=6

Next c. Knapsack Capacity left = 6-3=3

Next e. But we can take just half of 'e' as knapsack capacity left is just 3.

Total profit = profit for 'a' + profit of d + profit of c + (profit of e) /2

= 15 + 16 + 9 + 8.5

=48.5
selected by
Answer:

Related questions

2 votes
2 votes
2 answers
2
Bikram asked May 26, 2017
341 views
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
1 votes
1 votes
2 answers
3
Bikram asked May 26, 2017
454 views
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
0 votes
0 votes
1 answer
4
Bikram asked May 26, 2017
284 views
Let $T$ be a rooted ternary tree where each internal node of $T$ has a maximum of $3$ children. If root is at depth $0$, then maximum total number of vertices $T$ can hav...