fractional-knapsack.md (1296B)
1 +++ 2 title = "Fractional knapsack" 3 template = "page-math.html" 4 +++ 5 6 # Fractional knapsack 7 8 ## Problem 9 take as much as as possible from best benefit per weight ratio. 10 11 (Benefit,Weight) = {(12, 4), (10, 6), (8, 5), (11, 7), (14, 3), (7, 1), (9, 6)} 12 Total Weight (W) = 18 13 14 ## Solution 15 Build a table, and calculate the B/W ratio for each entry: 16 17 | | | | | 18 | --- | --- | --- | --- | 19 | S | B | W | R=B/W | 20 | 1 | 12 | 4 | 3 | 21 | 2 | 10 | 6 | $1 \frac{4}{6}$ | 22 | 3 | 8 | 5 | $1 \frac{3}{5}$ | 23 | 4 | 11 | 7 | $1 \frac{4}{7}$ | 24 | 5 | 14 | 3 | $1 \frac{2}{2}$ | 25 | 6 | 7 | 1 | 7 | 26 | 7 | 9 | 6 | $1 \frac{1}{2}$ | 27 28 W = 18. 29 30 Start taking by highest ratio. 31 Formula: 32 33 $B_{\text{S with highest ratio}}\times\frac{\text{items taken}}{weight}$ 34 35 36 37 <table> 38 <tr><td><strong>Item<strong></td><td>$B_6\times\frac{1}{1}$</td><td>$B_5\times\frac{3}{3}$</td><td>$B_1\times\frac{4}{4}$</td><td>$B_2\times\frac{6}{6}$</td><td>$B_3\times\frac{4}{5}$</td></tr> 39 <tr><td><strong>Cum.totalweight<strong></td><td>1</td><td>4</td><td>8</td><td>14</td><td>18</td></tr> 40 </table> 41 42 43 For total profits, calculate the addition of all items. 44 45 ## Complexity 46 47 if S is a heap-based priority queue, with highest benefit per weight value having highest priority, 48 49 then in O(nlogn)