GATE CSE 2018 | Question: 48

Question

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 ____

Comments

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

---

How optimal algorithm is working here, please show the steps.

---

https://gateoverflow.in/204123/gate2018-48#a204237

---

"may not split"??>>>>>may also split??Possible??

its bit confusing they should mention directly.

---

no item may be split apply in not in optimal greedy also

Answer 1

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

Comments

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

Can Dynamic Approach gives optimal solution always ??

---

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.

---

This question doesn’t make any sense if splitting is allowed because they given values in such a manner that while choosing the values in greedy, you may either able to take the V/W (maximum values then not able to take all subsequent decreasing V/W values) or you can’t able to fill the weight you have given (11 KG).

 

Now let’s analyse whatever i said . --

1 –   if splitting is allowed then in (Greedy) :--

Item no. 4 fully and partial item 1 is filled. giving

total value = 24+ (60/10)*9 = 78 (this is optimal also because you can’t get better than this.)

 

2 –  This question also does not make sense if we have to fill 12 kg weight and splitting is not allowed. 

total value (greedy) = (item 4 value + Item 1 value) = 24+60 = 74

(and again this is optimal also because you can’t get better than this.)

Answer 2

Answer = 16

Comments

for [4,8] it will be 44

Answer 3

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

Comments

Explain the optimal algorithm...

---

Search for 0/1 knapsack dynamic programming.

---

https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

Answer 4

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

Comments

Read the question again. It's asking total value difference.