609 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
349
349 views
GO Classes asked Sep 9, 2025
349 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
350
350 views
GO Classes asked Sep 9, 2025
350 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
322
322 views
GO Classes asked Sep 9, 2025
322 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
437
437 views
GO Classes asked Sep 9, 2025
437 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...