Gate 2018

Question

Value of V GREEDY - V OPT

Comments

Ans is in negative

---

I ALSO GOT ANS IN -VE

---

Ans is 16

60-44

They have mentioned not to take fractional part in greedy

---

But the main property of greedy is that we can take in fractions and also we take only that one whose profit is maximum if possible...

Not to take in fractions is for optimal one

Answer 1

It was Vopt -Vgreedy

Ans Maybe 16

Comments

I also write 16

---

60-44=16

---

how are they getting -ve do u have any idea??

---

my answer is 24. :-(

Answer 2

The Answer is 60 - 44 = 16.

It was a 0/1 Knapsack question. If you apply the optimal algorithm(Dynamic Programming), you will get 60 for Vopt.

If you apply the method that they listed, in the Vgreedy approach, you will get 44.

The answer cannot be negative, as it is a 0/1 knapsack so either the Optimal Algorithm will produce a result greater than or equal to the one produced by Greedy Approach.

Comments

They have asked not to have fractional part than is this the way it has tobe answered?

 

For optimal it is going to have value=60 and weight=10 and now we caanot have fractional value so vopt=60

 

and for greedy it has to 20+24 =44 i.e v2/w2 and v3/w3 addition so vgreedy=44

 

and then vopt-vgreedy=16

Is this the actual procedure?

 

Or do we just have to consider to neglect fractional portion in any one of the greedy or optimal case

 

please explain me

Answer 3

i think they have asked Vopt - Vgreedy