Вопрос о сортировке значений.

← →
Piton X (2005-11-30 09:31) [0]

Есть несколько величин (на самом деле это размеры нескольких файлов).
Есть некая эталонная величина (это размер болванки DVD).

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

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

← →
Digitman © (2005-11-30 09:44) [1]

задача из области комбинаторики.

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

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

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

← →
wal © (2005-11-30 09:52) [2]

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

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

С уважением.

← →
TUser © (2005-11-30 11:16) [3]

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

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

← →
Piton X (2005-11-30 14:36) [4]

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

С уважением.

← →
Digitman © (2005-11-30 14:42) [5]

модель дла поиска в Гугле - "алгоритм решения Задача о рюкзаке" ... туча ссылок на материалы

← →
jack128 © (2005-11-30 14:48) [6]

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

← →
DesWind © (2005-11-30 15:01) [7]

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

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

← →
wal © (2005-11-30 15:01) [8]

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

С уважением.

← →
Piton X (2005-11-30 15:59) [9]

Болванок сколько угодно, но нужно найти именно такое расположение файлов, которое бы позволило разместить их на болванке, максимально компактно. Это важно.
Т.е. как раз нужно найти вариант - засунуть два камня по 4 кг.

С уважением.

← →
wal © (2005-11-30 16:09) [10]

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

← →
Piton X (2005-11-30 18:01) [11]

Болванок много, но задача состоит в том, чтобы разместить файлы на них наиболеее компактно. Т.е., так, чтобы разместить файлы на как можно меньшем количестве болванок.

С уважением.

> 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 & <=1}; Sum(Xij) по j = 1; Yi >= 0
а минимизировать Sum(Vol - Yi), где Vol - емкость одного диска.
{Возможно, что я забыл еще какие-то ограничения}

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

--
Regards, LVT.

← →
Piton X (2005-12-01 08:58) [13]

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

Тысяча извенений - про NP-полноту я очень сильно соврал. Задача решается динамическим программированием.

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

Вопрос о сортировке значений. Найти похожие ветки