615 views
4 4 votes
Consider the weights and values of items listed below. Note that there is only one unit of each item.

\[
\begin{array}{|l|c|c|}
\hline
\text{Item number} & \text{Weight (in Kgs)} & \text{Value (in rupees)} \\
\hline
1 & 8 & 48 \\
2 & 5 & 30 \\
3 & 3 & 18 \\
4 & 1 & 12 \\
\hline
\end{array}
\]

The task is to pick a subset of these items such that their total weight is no more than 10 Kgs and their total value is maximized. Moreover, the item may be split. The total value of items picked by an optimal algorithm is denoted by $V_{\text {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_{\text {greedy }}$.

The value of $V_{\text {opt }}-V_{\text {greedy }}$ is __________.

3 Answers

5 5 votes
Since the items may be split

Hence greedy will be optimal algorithm here

That's why answer is 0
Answer:
Position:
Show:

Related questions

3 3 votes
2 2 answers
352
352 views
GO Classes asked Sep 9, 2025
352 views
We are given 8 tasks $T_1, T_2, \ldots, T_8$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ ...
2 2 votes
2 2 answers
355
355 views
GO Classes asked Sep 9, 2025
355 views
Consider the following functions:$$\begin{aligned}& \mathrm{f}(\mathrm{n})=3 \mathrm{n}^{\sqrt{\mathrm{n}}} \\& \mathrm{~g}(\mathrm{n})=2^{\sqrt{\mathrm{n}}\log _2{\mathr...
2 2 votes
2 2 answers
326
326 views
GO Classes asked Sep 9, 2025
326 views
If algorithm $A$ and another algorithm $B$ take $\log _2(n)$ and $\sqrt{ } n$ microseconds, respectively, to solve a problem, then the largest size $n$ of a problem these...
1 1 vote
2 2 answers
438
438 views
GO Classes asked Sep 9, 2025
438 views
Given a 2-D array mat where the elements of each row are sorted in non-decreasing order and the first element of a row is greater than the last element of the previous ro...