Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Cyberholic
0 / 0 / 0
Регистрация: 09.05.2011
Сообщений: 12
1

Получить наибольшее непрерывное количество свободного пространства в ряду на полках с минимальным количетсвом шагов

09.05.2011, 22:50. Просмотров 1486. Ответов 14
Метки нет (Все метки)

Доброго времени суток!

У меня стоит задача составить алгоритм, решающий описанные ниже задачи. К сожалению, я очень мало об этом знаю и пока в самом начале пути и подумала может знающие люди смогут подсказать направление.
СПАСИБО ОГРОМНОЕ заранее!

Итак задача:
Получить наибольшее непрерывное количество свободного пространства в ряду на полках с минимальным количетсвом шагов (перестановок книг на полке), показать вариант (как выглядит полка, какие книги где) с мин количеством шагов, с кол шагов min-1, min-2 и т.д.
Данные: Шкаф с полками и книгами на разных рядах. Надо максимизировать количество свободного пространства в РЯДУ. Есть несколько типов книг: роман, детектив и приключения. Роман нельзя перемещать, они должны остаться на своих местах. Все остальные можно свободно перемещать. Расстояние на полках и размер книг измеряем в миллиметрах.

Опция: отдавать предпочтение перемещению книг одного и того же автора, что бы они стояли рядом...

Вот так вот...
Спасибо за помощь!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2011, 22:50
Ответы с готовыми решениями:

Перед распаковкой архива, узнать количество свободного дискового пространства.
Перед распаковкой архива на сайте хочу узнать есть ли для этого свободное...

Определить и вывести диск который имеет наибольшее количество свободного места
Добрый день, у меня возникла проблема с powershell нужно написать как я понимаю...

Определение свободного дискового пространства
Помогите решить проблему, ни как не могу подобрать нужных параметров. Есть...

Определение свободного пространства на диске
Написать программу которая измеряет свободное пространство на любом...

Резкое и странное уменьшение свободного пространства
Только сейчас заметил.Свойства папок показывает одно,свойства диска другое.Анти...

14
Cyberholic
0 / 0 / 0
Регистрация: 09.05.2011
Сообщений: 12
20.07.2011, 12:57  [ТС] 2
Люди знающие, подскажите пожалуйста!
0
rew
0 / 0 / 0
Регистрация: 20.07.2011
Сообщений: 9
20.07.2011, 21:33 3
Cyberholic, надо на языке программирования???
0
Cyberholic
0 / 0 / 0
Регистрация: 09.05.2011
Сообщений: 12
21.07.2011, 10:37  [ТС] 4
Цитата Сообщение от rew Посмотреть сообщение
Cyberholic, надо на языке программирования???
Не обязательно! Мне нужно хотя бы словесно алгиритм/логику для написания программы

СПАСИБО!
0
oxotnik
1628 / 1101 / 75
Регистрация: 21.08.2008
Сообщений: 4,625
Записей в блоге: 1
21.07.2011, 10:41 5
1. Каждой книге присваивается "весовой" коэффициент.
2. Потом эти коэфф. вводятся в массив
3. Массив сортируется. (алгоритмов куча, можно найти уже готовые исходники)
4. Profit
ЗЫ: если через SQL делать, так вообще пара строк будет
0
rew
0 / 0 / 0
Регистрация: 20.07.2011
Сообщений: 9
21.07.2011, 10:48 6
Cyberholic, ну щас попробую составить , но не обещаю!
0
Cyberholic
0 / 0 / 0
Регистрация: 09.05.2011
Сообщений: 12
31.07.2011, 22:16  [ТС] 7
Цитата Сообщение от oxotnik Посмотреть сообщение
1. Каждой книге присваивается "весовой" коэффициент.
2. Потом эти коэфф. вводятся в массив
3. Массив сортируется. (алгоритмов куча, можно найти уже готовые исходники)
4. Profit
ЗЫ: если через SQL делать, так вообще пара строк будет
Я в этом абсолютный новичок! Почитала несколько сайтов/форумов по созданию алгоритмов и очень трудно с нуля "прыгнуть" в тему. Если не трудно помогите пожалуйста поподробнее.
Как будет определяться весовой коеффициент?
Алгоритм по сортировке массива? Как это работает?
И что такое Profit :-)

СПАСИБО БОЛЬШОЕ!

Добавлено через 53 секунды
Цитата Сообщение от rew Посмотреть сообщение
Cyberholic, ну щас попробую составить , но не обещаю!
:-) Попробуйте пожалуйста :-)
0
NIch
400 / 311 / 74
Регистрация: 17.03.2010
Сообщений: 1,120
31.07.2011, 23:59 8
Цитата Сообщение от Cyberholic Посмотреть сообщение
И что такое Profit :-)
http://lurkmore.ru/ПРОФИТ
1
BAIZOR
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
01.08.2011, 22:06 9
Нужно уточнить:
1)Что в приоритете, полностью отсортированый шкаф, или минимальное кол-во шагов?
2)Что считаеться за "шаг"?
3)Можно ли положить книгу на пол, и тем временем перебирать другие книги? и какое это будет иметь отношение к шагу?
4)Можно ли переложить все книги(кроме романов) на другую полку и тем самым максимизировать пространство на другой?
5)Передвижение книги по самое полке, и перекладывание между полками как относяться к шагу?

Добавлено через 7 минут
Уже начинает проглядываться алгоритм.
1)Надо найти полку в которой растояние между двумя близлежащими(это важно) романами(если они есть), или одним романом и стенкой(максимально далекой), или в лучшем случае вообще без них будет найбольшим.
2)Если таких несколько, тогда найти ту, на которой меньше книг.
3)Начать рабрасывать книги по другим полкам(все кроме той которую мы отметили).

Проблемы могут возникнуть в третьем этапе, возможен такой случай что книга не будет влазить, и для этого необходимо будет сдвигать книги на какойто полке, скорее всего будет оптимальнее сначала здвинуть книги на полке в плотную, а потом начать ее заполнять, но не стоит делать этого для тех полок которые мы не заполням!

Но я вам более детально продиктую алгоритм когда ответите на вопросы...
0
Cyberholic
0 / 0 / 0
Регистрация: 09.05.2011
Сообщений: 12
14.08.2011, 00:26  [ТС] 10
Цитата Сообщение от BAIZOR Посмотреть сообщение
Нужно уточнить:
1)Что в приоритете, полностью отсортированый шкаф, или минимальное кол-во шагов?
2)Что считаеться за "шаг"?
3)Можно ли положить книгу на пол, и тем временем перебирать другие книги? и какое это будет иметь отношение к шагу?
4)Можно ли переложить все книги(кроме романов) на другую полку и тем самым максимизировать пространство на другой?
5)Передвижение книги по самое полке, и перекладывание между полками как относяться к шагу?

Добавлено через 7 минут
Уже начинает проглядываться алгоритм.
1)Надо найти полку в которой растояние между двумя близлежащими(это важно) романами(если они есть), или одним романом и стенкой(максимально далекой), или в лучшем случае вообще без них будет найбольшим.
2)Если таких несколько, тогда найти ту, на которой меньше книг.
3)Начать рабрасывать книги по другим полкам(все кроме той которую мы отметили).

Проблемы могут возникнуть в третьем этапе, возможен такой случай что книга не будет влазить, и для этого необходимо будет сдвигать книги на какойто полке, скорее всего будет оптимальнее сначала здвинуть книги на полке в плотную, а потом начать ее заполнять, но не стоит делать этого для тех полок которые мы не заполням!

Но я вам более детально продиктую алгоритм когда ответите на вопросы...
1) В приоритете и то и другое. То есть нужно определить каково может быть максимально возможное пустое пространство и как его достич с минимальным количеством шагов.
2) один шаг в данном случае -- это любая перестановка на полке, с полки на полку или даже просто сдвиг книги
3) Все книги должны быть на полке, на пол к сожалению нельзя...
4) Можно. Но ведь не факт, что это пространство будет наибольшим непрерывным, все зависит от начального расположения книг
5) Передвижение книги на одной полке а так же с полки на полку -- все считается за шаг

Расстояние между книгами и толщину книг в миллиметрах...

СПАСИБО БОЛЬШОООООЕ!
0
ValeryLaptev
Эксперт С++
1051 / 830 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
14.08.2011, 13:43 11
Cyberholic, постановка СИЛЬНО похожа на задачу дефрагментации диска. Подумайте на эту тему... Книги одного автора - это блоки одного файла. Романы перемещать нельзя - это системные блоки...
0
Cyberholic
0 / 0 / 0
Регистрация: 09.05.2011
Сообщений: 12
16.08.2011, 23:56  [ТС] 12
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Cyberholic, постановка СИЛЬНО похожа на задачу дефрагментации диска. Подумайте на эту тему... Книги одного автора - это блоки одного файла. Романы перемещать нельзя - это системные блоки...
Деиствително похожи задачи с разницеи что мне нужно минималное количество шагов. Я искала алгоритм дефрагментации диска (словесниы), но ничего не нашла по етои теме! Потому и спрашиваю профессионалаво о помоши!

Пожалуиста!
0
mac_alleb
7 / 7 / 0
Регистрация: 05.08.2011
Сообщений: 54
17.08.2011, 09:21 13
Я так понял, задача по другому называется оптимизация пространства для файлов на диске ?
Алгоритм следующий:
1) дать номер каждой книге (оригинальный) в котором учмтывался бы автор и тип книги.
2) отсортировать быстрым алгоритмом сортировки (алгоритм прилагается) книги с записью их номеров
в другой массив, не сортируя запрещенные (алгоритм это позволяет).
3)отсортировать одновременно два массива: номер места на полке для запрещенной книги и расстояние
между ближайшими запрещенными книгами (мой алгоритм быстрой сортировки это не позволяет,
на то она и быстрая ) можно пузырьком (других алгоритмов сортировки двух массивов одновременно
я просто не знаю, если знаете - подскажите ).
4) подсчитать количество томов для каждой книти в массиве из п.2
5) перебрать напрямую количество томов и расстояние между ближайшими запрещенными книгами
полученными в п.2 и п.3 и расставить книги в соответствии с перебором
В конце останется свободное место после оптимизации .
Алгоритм быстрой сортировки (для массива целых чисел):
1) инициализовать массив по размеру равный максимальному числу сортируемого массива
2) при пробегании сортируемого массива (1 проход !!!! ) заносить в ячейку вспомогательного из п.1
с номером равным рассматриваемому числу единицу
3) если номер встретился еще раз, добавить в соответствующую ячейку еще 1
4) после прохода по сортируемому массиву переписать его следующим образом: плотно заполнить
ячейки начиная с первой числами равными номеру ячейки вспомогательного массива, если в
ячейке 0, то ничего не заносить, если есть какое-то число, то повторить в сортируемом массиве
этот номер ячейки согласно количеству из этого числа
Вот и все .
0
Cyberholic
0 / 0 / 0
Регистрация: 09.05.2011
Сообщений: 12
23.08.2011, 00:02  [ТС] 14
С оптимизацией я более менее разобралась. Вот никак не соображу следующее:
Если есть начальный вид полки с книгами и конечный вид полки с оптимизированным пространством как найти минимальное количество перестановок книг за которое можно получить данный конечный результат???
0
ValeryLaptev
Эксперт С++
1051 / 830 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
23.08.2011, 08:45 15
Cyberholic, задача - на динамическое программирование, похоже.
0
23.08.2011, 08:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2011, 08:45

4х слойная плата и заливка свободного пространства
Добра! Сделал 4-слойную плату, уже почти отдал в производство и тут меня...

Не получается сделать разметку свободного пространства
Здравствуйте , я выделил 20 гб для второй системы , уже хотел установить , но...

Жётский. пропала часть свободного пространства
такой вот вопрос. 1 тб. вдруг пропало 50-60 гб свободного пространства. жётски...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru