Том 1, номер 4, 1994 г., Стр. 53-63
УДК 519.854.3
Ю. В. Шамардин
О точности некоторых алгоритмов загрузки ранца
Аннотация:
Изучается алгоритм и его модификация, приближенно решающие задачу максимального заполнения ранца ограниченной вместимости предметами из заданного списка. Выясняются значения минимальных отношений весов приближенной и наилучшей загрузок, когда веса предметов не превосходят заданной доли от вместимости ранца.
Библиогр. 1.
Шамардин Ю. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 29 июля 1994 г.
|