Вариант 4062455599.
Найдите неверное утверждение:
Задачи 3SAT и 2SAT:
С какой точностью работает «чисто» жадный алгоритм для задачи о рюкзаке («хватать предметы по убыванию удельной стоимости, пока не кончится место в рюкзаке»)?
Какова наилучшая сложность алгоритма из темы про FPTAS-алгоритмы для рюкзака?
Задача 2SAT: