Лексикографический $0{,}5$-приближенный алгоритм для задачи о многих ранцах

Предложен алгоритм для задачи о многих ранцах (MKP). Алгоритм использует упорядочение ранцев по неубыванию размера и два упорядочения объектов: по невозрастанию полезности и невозрастанию отношения полезности к размеру объекта. Эти упорядочения порождают два отношения лексикографического порядка на множестве $A\times B$ (здесь $A$ – множество ранцев и $B$ – множество неделимых объектов). По каждому лексикографическому упорядочению алгоритм строит допустимое решение MKP, просматривая пары $(a,b)\in A\times B$ в соответствующем порядке и помещая объект $b$ в ранец $a$, если объект еще не размещен и в ранце достаточно места. Из двух полученных решений алгоритм выбирает лучшее. Алгоритм имеет относительную точность $0{,}5$ и трудоемкость $O(mn)$ (без учета сортировок), где $m$ и $n$ – мощности множеств $A$ и $B$ соответственно.