/
xddxdd
/
Python
Обзор
Документация
Войти
/
xddxdd
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
greedy_methods/fractional_knapsack.py
51 строка
1 KB
Hardik Pawar
Add doctests for fractional knapsack (#10891)
24 окт 2023, 17:36
Не верифицирован
24 окт 2023, 17:36
aeee0f4
Код
Авторство
О чём код?
from bisect import bisect from itertools import accumulate def frac_knapsack(vl, wt, w, n): """ >>> frac_knapsack([60, 100, 120], [10, 20, 30], 50, 3) 240.0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 10, 4) 105.0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, 4) 95.0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6], 8, 4) 60.0 >>> frac_knapsack([10, 40, 30], [5, 4, 6, 3], 8, 4) 60.0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 0, 4) 0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, 0) 95.0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], -8, 4) 0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, -4) 95.0 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 800, 4) 130 >>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, 400) 95.0 >>> frac_knapsack("ABCD", [5, 4, 6, 3], 8, 400) Traceback (most recent call last): ... TypeError: unsupported operand type(s) for /: 'str' and 'int' """ r = sorted(zip(vl, wt), key=lambda x: x[0] / x[1], reverse=True) vl, wt = [i[0] for i in r], [i[1] for i in r] acc = list(accumulate(wt)) k = bisect(acc, w) return ( 0 if k == 0 else sum(vl[:k]) + (w - acc[k - 1]) * (vl[k]) / (wt[k]) if k != n else sum(vl[:k]) ) if __name__ == "__main__": import doctest doctest.testmod()