retagged by
21,936 views
38 votes
38 votes
Consider the weights and values of items listed below. Note that there is only one unit of each item.
$$\begin{array}{|c|c|c|}\hline \textbf{Item number}  &  \textbf{Weight (in Kgs) }& \textbf{Value (in rupees)} \\\hline  \text{$1$} & \text{$10$} & \text{$60$} \\\hline  \text{$2$} & \text{$7$} & \text{$28$} \\\hline \textbf{$3$} & \text{$4$} & \text{$20$} \\\hline  \text{$4$} & \text{$2$} & \text{$24$}  \\\hline \end{array}$$
The task is to pick a subset of these items such that their total weight is no more than $11$ Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by $V_{opt}$. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by $V_{greedy}$.

The value of $V_{opt}-V_{greedy}$ is ____
retagged by

5 Answers

Best answer
56 votes
56 votes

$V_{opt}$ is clearly $60$. You can go for brute force or by normal intuition you can get it.

Now solving for $V_{greedy}$.

$$\begin{array}{|c|c|c|c|}\hline \textbf{Item name}  &  \textbf{Weight (in Kgs) }& \textbf{Value (in Rupees)} & \textbf{Value/Weight} \\\hline  \text{1} & \text{10} & \text{60} & \text{6} \\\hline  \text{2} & \text{7} & \text{28} & \text{4} \\\hline \text{3} & \text{4} & \text{20} & \text{5} \\\hline  \text{4} & \text{2} & \text{24} & \text{12} \\\hline \end{array}$$

Sort them in descending order of Value/Weight as per the question.
$$\begin{array}{|c|c|c|c|}\hline \textbf{Item name}  &  \textbf{Weight (in Kgs) }& \textbf{Value (in Rupees)} & \textbf{Value/Weight} \\\hline  \text{4} & \text{2} & \text{24} & \text{12} \\\hline  \text{1} & \text{10} & \text{60} & \text{6} \\\hline \text{3} & \text{4} & \text{20} & \text{5} \\\hline  \text{2} & \text{7} & \text{28} & \text{4} \\\hline \end{array}$$
Now start picking items.(Note: You cannot take a fraction of the given weight as per the question). Max weight size is given as $11$(Inclusive).

  • Item $4$ is picked. Weight remaining = $11-2 = 9$kg.
  • Item $1$ cannot be picked as $10$kg $>9$kg.
  • Item $3$ can be picked as $4$kg $<$ $9$kg. Weight Remaining = $9-4 = 5$kg
  • Item $2$ cannot be picked as $7$kg $>5$kg.

So, item $4$ and Item $3$ are picked. Their values are $24$ and $20$ respectively.

$\implies V_{greedy} = 24+20 = 44.$

$V_{optimal} - V_{greedy}= 60 - 44 = 16.$

edited by
9 votes
9 votes
If we apply the optimal method the most we can get is by including Item no. 1 i.e 10kg and value is 60.

Now applying the greedy method we will first pickup weight no. 4 because of its (value/weight) value is highest, then pick Item no. 1 but we can't include it because the overall weight will be more than required, then pick Item no. 3 and similarly we can't include item no. 2.

So greedy picks item no. 4 and item no. 3. Overall profit by greedy = 20+24=44.

Vopt -Vgreedy = 60-44 =16
7 votes
7 votes

Greedy Algorithm will pick item with highest value of value / weight provided that total value doesn't exceed 11 kg. (maximum weight)

Item Number  Weight Value
4 2 24
3 4 20
Total   44

Optimal Algorithm will pick

Item Number Weight Value
1 10 60
Total   60

So value Optimal - Value greedy = 60 - 44 = 16

Answer:

Related questions

0 votes
0 votes
3 answers
1
Ashok asked Feb 4, 2018
1,826 views
Value of V GREEDY - V OPT
35 votes
35 votes
9 answers
2
gatecse asked Feb 14, 2018
17,335 views
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...
35 votes
35 votes
7 answers
3