18.10.2018, 09:24 [+3 UTC]
в нашей команде: 3 015 чел. | участники онлайн: 3 (рекорд: 21)

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

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

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.51 (29.09.2018)

Общие новости:
24.09.2018, 16:49

Форум:
14.10.2018, 19:20

Последний вопрос:
18.10.2018, 02:57

Последний ответ:
18.10.2018, 08:14

Последняя рассылка:
17.10.2018, 23:45

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

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

Наша кнопка:

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

Отзывы о нас:
01.01.2017, 01:24 »
svrvsvrv
Огромное спасибо за такой обстоятельный ответ. [вопрос № 190361, ответ № 274499]
28.06.2010, 16:09 »
Dimon4ik
Спасибо. На счет официального названия - я тоже думаю, что его нет. Так как тоже не находил. [вопрос № 179333, ответ № 262315]
12.11.2009, 08:01 »
jeck26
Огромное спасибо за ответ! Сначала буду искать недорогой привод. Если не найду, куплю внешний USB 2.0 за 2 т. р. [вопрос № 174133, ответ № 256379]

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

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

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

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

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 124
solowey
Статус: Студент
Рейтинг: 72
Андрей Кузнецов aka Dr_Andrew
Статус: Старший модератор
Рейтинг: 24

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

Консультация онлайн # 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.14270 сек.

© 2001-2018, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.51 от 29.09.2018