Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Вопрос о сортировке значений. [D6, WinXP]

Piton X © (2005-11-30 09:31:00)
Есть несколько величин (на самом деле это размеры нескольких файлов).
Есть некая эталонная величина (это размер болванки DVD).

Нужен такой алгоритм сортировки этих величин (размеров файлов), чтобы наиболее компактно разместить их на этот DVD.
Метод простого перебора вариантов не подходит, так как может работать только при небольшом количестве величин. Если же величин (файлов) много, то количество вариантов их компоновки увеличивается в прогрессии (все мы помним легенду о шахматной доске и зернах).
Вопрос к вам уважаемые мастера. Может быть, есть какой-нибудь алгоритм или способ, раскидать все эти файлы разного размера, по относительно равным "кучкам", да еще так, чтобы эти кучки наиболее плотно помещались на DVD?

Заранее благодарен за ответы. :-)

TUser (2005-12-01 12:53:00) [1]
Тысяча извенений - про NP-полноту я очень сильно соврал. Задача решается динамическим программированием.

Еще раз извини.

wal (2005-12-01 09:03:00) [2]

> чтобы разместить файлы на как можно меньшем количестве болванок.
Тогда [2]. Только с учетом того, что если после 7. список еще не пуст, то переходим на 2.

Piton X (2005-12-01 08:58:00) [3]
Всем спасибо. Вариант - wal © (30.11.05 09:52), взят на вооружение.

С уважением.

Leonid Troyanovsky (2005-11-30 19:03:00) [4]

> Piton X (30.11.05 18:01) [11]
> Болванок много, но задача состоит в том, чтобы разместить
> файлы на них наиболеее компактно. Т.е., так, чтобы разместить
> файлы на как можно меньшем количестве болванок.

Честно говоря, я основательно забыл то, чему меня когда-то
учили, но рискнул бы попробывал в лоб, через Excel & Solver (.xla).
Т.е., испытал линейную модель:

a1*x11 + a2 *x12 +... = y1 {Байтов на первом диске}
a1*x21 + a2 *x22 ... = y2 {Байтов на втором диске}
и т.д., где Ai - размер файла.
Причем, Xij = (0, 1) {ц.ч., >=0 & = 0
а минимизировать Sum(Vol - Yi), где Vol - емкость одного диска.
{Возможно, что я забыл еще какие-то ограничения}

Т.е., попробывать на чем-то обозримом, а в случае неудачи
продолжить поиски более подходящей модели.

--
Regards, LVT.

Piton X (2005-11-30 18:01:00) [5]
Болванок много, но задача состоит в том, чтобы разместить файлы на них наиболеее компактно. Т.е., так, чтобы разместить файлы на как можно меньшем количестве болванок.

С уважением.

wal (2005-11-30 16:09:00) [6]

> Болванок сколько угодно
> разместить их на болванк е
Дак все таки на одной или на нескольких?

Piton X (2005-11-30 15:59:00) [7]
Болванок сколько угодно, но нужно найти именно такое расположение файлов, которое бы позволило разместить их на болванке, максимально компактно. Это важно.
Т.е. как раз нужно найти вариант - засунуть два камня по 4 кг.

С уважением.

DesWind (2005-11-30 15:01:00) [8]

> jack128 © (30.11.05 14:48) [6]

Я правда не знаю формулировки "Задачи о рюкзаке", но два 4кг, по предложеному алгоритму войдут в следующий рюкзак, а надо распихать все "камни", судя по вопросу.

wal (2005-11-30 15:01:00) [9]

> [6] jack128 © (30.11.05 14:48)
Значит я задачу понял неправильно понял. Когда увидел волшебную фразу "это размер болванки DVD", то решил, что нужно просто минимизировать пустое место на несколькихболванках, ибо если на одну все влезает, то задача смысла не имеет, а если не влезает, а второй нет, то руководствуются, обычно, несколько иным принципами отсеивания не подлежащих записи файлов, чем их размер.
В таком случае эти 2 по 4 всего лишь попадут на вторую болванку, а не на первую.

С уважением.

jack128 (2005-11-30 14:48:00) [10]
wal © (30.11.05 9:52) [2]
размер рюкзака 10. Один камень - 7, два других по 4. По твоему решению выходит, что эффективнее всего запишнуть один 7кг камень, тогда как в реальности лудше - 2 камня по 4кг.

Digitman (2005-11-30 14:42:00) [11]
модель дла поиска в Гугле - "алгоритм решения Задача о рюкзаке" ... туча ссылок на материалы

Piton X (2005-11-30 14:36:00) [12]
//Digitman © (30.11.05 09:44) [1]
задача из области комбинаторики.
весьма схожа с "Задачей о рюкзаке"//
Спасибо за ответы.
Нельзя ли подробнее? По ссылке сходил, но именно "задача о рюкзаке" написана на английском, а я с ним "не очень". Не могли бы вы коротко сформулировать что это за задача и как она решается?

С уважением.

TUser (2005-11-30 11:16:00) [13]

> Digitman © (30.11.05 09:44) [1]

Это дискретная задача о рюкзаке. Они NP-полная, но есть эвристические алгоритмы ее приблизительного решения.

wal (2005-11-30 09:52:00) [14]
1. Создаем список размеров (для удобства отсортированный)
2. Задаем переменную (V), равную объему
3. Ищем наибольший, но не превышающий V размер
4. Если нашли, то 5, иначе 7
5. Удаляем найденный из списка, уменьшаем V на соответствующее значение.
6. Цикл на 3
7. Больше ничего впихать нельзя или все уже запихали.

Это, конечно, примитив. В реальности нузно учитывать размеры кластеров и т.д.

С уважением.

Digitman (2005-11-30 09:44:00) [15]
задача из области комбинаторики.

весьма схожа с "Задачей о рюкзаке"

посмотри здесь

http://algolist.manual.ru/maths/combinat/index.php

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »