>>> value = [1, 3, 5, 7, 9] >>> weight = [0.9, 0.7, 0.5, 0.3, 0.1] >>> fractional_knapsack(value, weight, 5) (25, [1, 1, 1, 1, 1]) >>> fractional_knapsack(value, weight, 15) (25, [1, 1, 1, 1, 1]) >>> fractional_knapsack(value, weight, 25) (25, [1, 1, 1, 1, 1]) >>
(
value: list[int], weight: list[int], capacity: int
)
| 6 | |
| 7 | |
| 8 | def fractional_knapsack( |
| 9 | value: list[int], weight: list[int], capacity: int |
| 10 | ) -> tuple[float, list[float]]: |
| 11 | """ |
| 12 | >>> value = [1, 3, 5, 7, 9] |
| 13 | >>> weight = [0.9, 0.7, 0.5, 0.3, 0.1] |
| 14 | >>> fractional_knapsack(value, weight, 5) |
| 15 | (25, [1, 1, 1, 1, 1]) |
| 16 | >>> fractional_knapsack(value, weight, 15) |
| 17 | (25, [1, 1, 1, 1, 1]) |
| 18 | >>> fractional_knapsack(value, weight, 25) |
| 19 | (25, [1, 1, 1, 1, 1]) |
| 20 | >>> fractional_knapsack(value, weight, 26) |
| 21 | (25, [1, 1, 1, 1, 1]) |
| 22 | >>> fractional_knapsack(value, weight, -1) |
| 23 | (-90.0, [0, 0, 0, 0, -10.0]) |
| 24 | >>> fractional_knapsack([1, 3, 5, 7], weight, 30) |
| 25 | (16, [1, 1, 1, 1]) |
| 26 | >>> fractional_knapsack(value, [0.9, 0.7, 0.5, 0.3, 0.1], 30) |
| 27 | (25, [1, 1, 1, 1, 1]) |
| 28 | >>> fractional_knapsack([], [], 30) |
| 29 | (0, []) |
| 30 | """ |
| 31 | index = list(range(len(value))) |
| 32 | ratio = [v / w for v, w in zip(value, weight)] |
| 33 | index.sort(key=lambda i: ratio[i], reverse=True) |
| 34 | |
| 35 | max_value: float = 0 |
| 36 | fractions: list[float] = [0] * len(value) |
| 37 | for i in index: |
| 38 | if weight[i] <= capacity: |
| 39 | fractions[i] = 1 |
| 40 | max_value += value[i] |
| 41 | capacity -= weight[i] |
| 42 | else: |
| 43 | fractions[i] = capacity / weight[i] |
| 44 | max_value += value[i] * capacity / weight[i] |
| 45 | break |
| 46 | |
| 47 | return max_value, fractions |
| 48 | |
| 49 | |
| 50 | if __name__ == "__main__": |