Задача: даны n предметов весом Xi и n корзин с одинаковой вместимостью V, V больше либо равно максимальному из Xj. нужно разместить все предметы в как можно меньшем количестве корзин

Алгоритм: берём предметы в порядке появления. Ищем первую уже использованную корзину, которая вместит предмет, если такой нет, используем новую.

Доказать, что алгоритм ошибается не более чем в 2 раза.(2-приближенный)

Доказать, что алгоритм не является (1.5 - eps) приближенным, для любого eps > 0

задан 4 Апр 11:23

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×237
×71
×3

задан
4 Апр 11:23

показан
42 раза

обновлен
4 Апр 11:23

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru