19.02.2019, 19:20 [+3 UTC]
в нашей команде: 3 396 чел. | участники онлайн: 9 (рекорд: 21)

:: РЕГИСТРАЦИЯ

задать вопрос

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.69 (10.02.2019)
JS-v.1.33 | CSS-v.3.35

Общие новости:
10.02.2019, 21:59

Форум:
16.02.2019, 15:03

Последний вопрос:
19.02.2019, 18:36
Всего: 148779

Последний ответ:
19.02.2019, 15:57
Всего: 257802

Последняя рассылка:
19.02.2019, 19:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
06.10.2010, 23:44 »
Kreaman
Спасибо большое за работу. Очень благодарен за помощь. [вопрос № 180184, ответ № 263362]
28.09.2017, 22:01 »
svrvsvrv
Спасибо за подробную, обстоятельную консультацию. [вопрос № 191395, ответ № 275302]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Коцюрбенко Алексей Владимирович
Статус: Модератор
Рейтинг: 682
solowey
Статус: Студент
Рейтинг: 363
zdwork
Статус: 1-й класс
Рейтинг: 111

Перейти к консультации №:
 

Консультация онлайн # 193386
Раздел: • С / С++
Автор вопроса: 111natasha11 (Посетитель)
Отправлена: 12.06.2018, 16:45
Поступило ответов: 0

Добрый день!
Дана задача: Существует N контейнеров, в каждый помещается ровно 1 кг какого-нибудь груза (объем груза значения не имеет). Есть M предметов, вес каждого предмета от 0 до 1 кг (объем не имеет значения).
Стоит задача о распределении этих предметов по контейнерам, чтобы количество используемых контейнеров было минимально возможным. Предполагается, что количество контейнеров и количество предметов может быть довольно большим (N <= 1000, M <=10000). Если предметы разложить не удается (например, суммарный вес предметов больше чем N кг), то выдать сообщение об этом.

Я её решила так: Вначале отсортировала массив предметов, которые надо положить в контейнеры; потом шла по отсортированному массиву с начала и конца, собирая большой предмет и сколько помещается к нему маленьких.

Получилась довольно большая сложность у алгоритма.

Как можно уменьшить сложность алгоритма? Какие ещё варианты решения существуют?



Приложение:

Состояние: Консультация закрыта

Oтветов пока не поступило.

Мини-форум консультации № 193386
mklokov
6-й класс

ID: 400828

# 1

 +1 
 
= общий = | 13.06.2018, 18:35 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Насколько я понимаю, это - модификация "задачи о ранце".
Решается или динамическим программированием, или методом ветвей и границ.

Асмик Гаряка
Советник

ID: 230118

# 2

= общий = | 14.06.2018, 13:50 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
111natasha11:

Пишите мне на почту.

 

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.18671 сек.

© 2001-2019, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.69 от 10.02.2019
Версия JS: 1.33 | Версия CSS: 3.35