23.06.2018, 22:53 [+3 UTC]
в нашей команде: 2 855 чел. | участники онлайн: 1 (рекорд: 21)

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

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

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

:: правила

:: новости

:: участники

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

:: форум

:: блоги

:: поиск

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

:: наш журнал

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

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

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

:: поддержка

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

Версия системы:
7.47 (16.04.2018)

Общие новости:
13.04.2018, 10:33

Форум:
18.06.2018, 08:55

Последний вопрос:
23.06.2018, 07:43

Последний ответ:
23.06.2018, 18:27

Последняя рассылка:
23.06.2018, 22:15

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

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

Наша кнопка:

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

Отзывы о нас:
16.02.2017, 22:29 »
Duns
Скорее всего так оно и есть. Вариант с PSI SATA контроллером стоит рассмотреть [вопрос № 190556, ответ № 274650]
16.08.2009, 18:01 »
Semiotic
Спасибо все спецам за их отзывчивость по любому поводу, за их ангельское терпение к безграмотным, ленивым и тупым вопросителям!

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

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

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

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

CradleA
Статус: Профессор
Рейтинг: 147
solowey
Статус: Студент
Рейтинг: 88
Асмик Гаряка
Статус: Советник
Рейтинг: 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.13954 сек.

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