13.12.2018, 01:34 [+3 UTC]
в нашей команде: 3 219 чел. | участники онлайн: 4 (рекорд: 19)

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

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

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

:: правила

:: новости

:: участники

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

:: форум

:: блоги

:: поиск

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

:: наш журнал

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

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

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

:: поддержка

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

Версия системы:
7.58 (11.12.2018)

Общие новости:
01.12.2018, 22:30

Форум:
08.12.2018, 14:26

Последний вопрос:
12.12.2018, 18:21

Последний ответ:
12.12.2018, 10:25

Последняя рассылка:
12.12.2018, 23:15

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

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

Наша кнопка:

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

Отзывы о нас:
28.05.2010, 23:24 »
Гальцов Андрей
Спасибо, спасибо, спасибо!... [вопрос № 178572, ответ № 261733]
14.11.2010, 11:48 »
Мироненко Николай Николаевич
Аа, факториал берём, понял! Спасибо Вам большое smile [вопрос № 180732, ответ № 264025]
08.05.2010, 12:17 »
Королев Олег Владимирович
Удовлетворил ответ спасибо. [вопрос № 178192, ответ № 261279]

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

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

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

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

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

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

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

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