6.9k views
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 ____

edited | 6.9k views
+18
Moreover, no item may be split. Most important line of the question,I missed this and got ans 18 :-(
0
How optimal algorithm is working here, please show the steps.
0
"may not split"??>>>>>may also split??Possible??

its bit confusing they should mention directly.
0
no item may be split apply in not in optimal greedy also

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

Is it because of below statement in question we have not picked item -3 and item -2 which would result in Vgreedy : 48 and had we picked item - 4 and item -2 Vgreedy 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
Can you please explain how to calculate voptimal ???
0
by Dynamic programming : 0/1 knapsack algorithm
0
If it was not easy to find Voptimal...then can we use dynamic approach ..

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. Answer = 16

+1
for [4,8] it will be 44
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
0
Explain the optimal algorithm...
0
Search for 0/1 knapsack dynamic programming.

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

+1