take as much as as possible from best benefit per weight ratio.
(Benefit,Weight) = {(12, 4), (10, 6), (8, 5), (11, 7), (14, 3), (7, 1), (9, 6)} Total Weight (W) = 18
Build a table, and calculate the B/W ratio for each entry:
| S | B | W | R=B/W |
| 1 | 12 | 4 | 3 |
| 2 | 10 | 6 | $1 \frac{4}{6}$ |
| 3 | 8 | 5 | $1 \frac{3}{5}$ |
| 4 | 11 | 7 | $1 \frac{4}{7}$ |
| 5 | 14 | 3 | $1 \frac{2}{2}$ |
| 6 | 7 | 1 | 7 |
| 7 | 9 | 6 | $1 \frac{1}{2}$ |
W = 18.
Start taking by highest ratio. Formula:
$B_{\text{S with highest ratio}}\times\frac{\text{items taken}}{weight}$
| Item | $B_6\times\frac{1}{1}$ | $B_5\times\frac{3}{3}$ | $B_1\times\frac{4}{4}$ | $B_2\times\frac{6}{6}$ | $B_3\times\frac{4}{5}$ |
| Cum.totalweight | 1 | 4 | 8 | 14 | 18 |
For total profits, calculate the addition of all items.
if S is a heap-based priority queue, with highest benefit per weight value having highest priority,
then in O(nlogn)