FPTAS for knapsack problem

Постановка задачи

Имеется набор из n предметов. У каждого предмета есть положительный вес w и неотрицательная стоимость c. Также дано неотрицательное число W - вместимость рюкзака. Требуется найти такое множетсво предметов M, чтобы они помещались в рюкзак, и суммарная стоимость предметов была максимальна. То есть
sum(c(x)) -> max, где x из M
при условии sum(w(x)) <= W, где x из M

Асимптотика и точность

Алгоритм решает задачу за O(n^3/eps) c точностью (1-eps), то есть OUTPT >= (1-eps)*OPT

Тестирование

Для запуска тестирования достаточно запустить файл stress.py