Register

Gate 2018

• retagged by
1,893 views
0 votes
0 votes
Value of V GREEDY - V OPT
• retagged by
User Avatar

3 Answers

1 votes
1 votes
It was Vopt -Vgreedy

Ans Maybe 16
User Avatar
0 votes
0 votes
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.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

38 votes
38 votes
5 answers
1
gatecse asked Feb 14, 2018
22,227 views
GATE CSE 2018 | Question: 48
Consider the weights and values of items listed below. Note that there is only one unit of each item. ... The total value of items picked by the greedy algorithm is denoted by $V_{greedy}$. The value of $V_{opt}-V_{greedy}$ is ____
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{Weigh...
User Avatar
35 votes
35 votes
9 answers
2
gatecse asked Feb 14, 2018
17,625 views
GATE CSE 2018 | Question: 47
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...
User Avatar
35 votes
35 votes
7 answers
3
gatecse asked Feb 14, 2018
13,168 views
GATE CSE 2018 | Question: 45
Consider the following program written in pseudo-code. Assume that $x$ and $y$ are integers. Count (x, y) { if (y !=1 ) { if (x !=1) { print("*"); Count (x/2, y); } else { y=y-1; Count (1024, y); } } } The number of times that the $print$ statement is executed by the call $Count(1024, 1024)$ is _____
Consider the following program written in pseudo-code. Assume that $x$ and $y$ are integers.Count (x, y) { if (y !=1 ) { if (x !=1) { print("*"); Count (x/2, y); } else {...
User Avatar
Link Copied!