**Moreover, no item may be split**. Most important line of the question,I missed this and got ans 18 :-(

The Gateway to Computer Science Excellence

+20 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 ____

$$\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 ____

+33 votes

Best answer

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

0

Is it because of below statement in question we have not picked item -3 and item -2 which would result in V_{greedy} **:** 48 and had we picked item - 4 and item -2 V_{greedy} would have been 52, does 0/1 knapsack algo(in general) take this into consideration by means of Dyn Programming or something else?

*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*

0

If it was not easy to find Voptimal...then can we use dynamic approach ..

Can Dynamic Approach gives optimal solution always ??

Can Dynamic Approach gives optimal solution always ??

0

https://en.wikipedia.org/wiki/Dynamic_programming

@jatin khachane 1 DP always gives optimal solution.

KS(i,w)= max{ Pi + KS(i-1,w-ai) , KS (i-1,w)} this equations says what is the value if we consider the object or if we ignore it. So it will always give optimal solution.

+8 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

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

+6 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

52,315 questions

60,427 answers

201,752 comments

95,227 users