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 ____
in Algorithms by
edited by | 6.9k views
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.
"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

5 Answers

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

edited by

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

Can you please explain how to calculate voptimal ???
by Dynamic programming : 0/1 knapsack algorithm
If it was not easy to find Voptimal...then can we use dynamic approach ..

Can Dynamic Approach gives optimal solution always ??

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

+12 votes

Answer = 16

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

Read the question again. It's asking total value difference.
0 votes
Vopt = 60
Vgreedy = 44, take profit/weight ratio, arrande in descending order, fill knapsack with integer unit only.
Vopt-Vgreedy = 16

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,427 answers
95,227 users