Стало быть сабж.
Вроде все написал, кроме одной вещи. Не могу придумать оптимальный алгоритм, для выборки из массива файлов, чтобы максимально забить ентой выборкой файлов саму болванку.

Что дано: на входе стало бы массив из файлов (директорий) и их размер, так же константа, в которой храниться размер болванки пустой (4.7 GB)
На выходе нужно получить непосредственно сам список, в котором просто будут именна директорий (файлов) для максимальной забивки болванки.

Помогите советом по алгоритму ...... а то дельного пока ничего не придумал.

Максим Для начала можно просто отсортировать по убыванию объёма, затем брать самые ёмкие, потом поменьше и так до 4.7e9 байтов. Только надо ещё каталоги от файлов отличать, не все каталоги можно разбивать на отдельные файлы.

Очень нужная прога! Дописывай

Rius
Ну скажем так ...... я как бы пишу прогу для себя и у меня все файлы (в основном фильмы) храняться в директориях соответствующих ....... сделал уже абсолютно все, кроме самой выборки ........

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

Методом полной переборки и сохранением просто ссылок на текущие варианты - енто тоже не выход ....... как бы такое написал, но при ентом машина загружается полностью секунд на 20, а енто как бы не правильно. Судя по всему ошибся где-то в реализации рекурсии и из-за этого происходит такой тормоз ..... дебагить времени не было, но думаю даже если бы нашел ошибку, то думаю не намного бы прибавило скорости

ser.spb
Пишу только для себя, так что не знаю кому она еще нужна

Известная комбинаторная задача, называется "Задача о рюкзаке". Точнее, одна из её разновидностей. В интернете куча материала. Первое, что попалось - http://www.uvk2.artn.ru/projects/Lopyre ... ukzac.html

Это почему же так? Раз тебе надо забить 4.7 то просто возми и забей их! Вариант такой. При достижении 4.7 (чуть меньше) если последубщий файл не влезает, откидываем и берем следующий (масси ведь сортирован уже от большего к меньшему) и так далее пока не забьем под завязку.

Ray Adams Это если не волнует потеря нескольких десятков-сотен метров. Хорошо бы действовало в случае с большим число разнокалиберных файлов, а с фильмами как-то неоднозначно.

p.s. я оставшееся место музыкой в mp3 забиваю, чтоб не пропадало, но решение с такой программой было бы лучше.

Rius Ну я лично уже привык, что при записи на DVD у меня влезает 6 фильмов и остается около 400 мегов, которые уже и забивать то нечем! Так, мелкий софт дописываю, обновления всякие. Все равно забуду где что. Так неужели жалко 200-400 мегов?

Добавлено спустя 1 минуту, 52 секунды:
Кстати и что за глупость

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

Ray Adams
Ну у меня так же влезает при обычном раскладе 6 фильмов и остается 200-320 метром, но енто не есть правильно ..... так как кодирую не только я, а мне еще кучу всего приносят ..... тем паче с выходом X264 уже не так важно 700 метров - кодировал уже 6 фильмов (достаточно короткие - 1.29-1.37) .... битрейт указываешь точный, чтобы получить 700 метров, но файл в сумме получается часто меньше 600 метров с ИДЕАЛЬНЫМ качеством ..... так что очень часто у меня валяются файлы меньше 650 метров, а с ними уже можно подумать о том, чтобы полностью забить болванку ..... тем паче все таки хочется даже при файлах в 700-716 MB (ну как показывает неро или енто 737 с чем-то миллионов байт) поместить столько всего, чтобы быть как можно ближе к концу болванки ..... потому что всегда есть шанс, что потом в какой-то момент из-за чуть более крупного файла (потом, например через месяц) попаду на такое, что болванка не будет записана полностью, потому что файл на 4 мега к примеру больше, чем может вместить болванка ..... все бывает

Rius
Я клипами забиваю свободное место

vor
Спасибки, почитаю
А ты оказывается не только можешь помочь по материнкам

Добавлено спустя 51 минуту, 49 секунд:
To All
Итак слепил исходник такой функции из блок-схемы ..... к сожалению на работе нема просто никаких средств программирования, так что не совсем знаю как все енто будет работать..... разумеется о переменных даже не задумывался

procedure Rucksack(N,Sum:integer;A:array[1..N] of integer;var L:integer;Results:array[1..L] of string;)
{процедура решает задачу о рюкзаке, т.е. находит такие подпоследовательности элементов массива A, сумма которых равна
Sum. Найденные последовательности помещаются в массив Results, каждая последовательность представляет строку номеров
элементов в нее входящих}
begin
Work:=True;
l:=0;
Top:=0;
SumT:=Sum;
m:=n;
while Work do
begin
while (SumT<A[m]) and(m>0) do
begin
m:=m-1
end;
if m=0
then
begin
if Top>0
then
begin
SumT:=SumT+A[Stack[Top]];
if Stack[Top]>1
then
begin
Stack[Top]:=Stack[Top]-1;m:=Stack[Top]-1;
SumT:=SumT-A[Stack[Top]];
end
else
begin
Top:=Top-1;
SumT:=SumT+A[Stack[Top]];
if Top=0
then
begin
Work:=False;
end
else
begin
Stack[Top]:=Stack[Top]-1;
m:=Stack[Top]-1;
SumT:=SumT-A[Stack[Top]];
end;
end;
end
else
begin
Work:=False;
end;
end
else
begin
Top:=Top+1;
while (SumT=A[m]) and(m>0) do
begin
Stack[Top]:=m;
l:=l+1;
i:=1;
s:='';
repeat
s:=s+','+IntToStr(Stack[i]);
i:=i+1
until not(i<=Top);
Results[l]:=s;
m:=m-1;
end;
if m<>0
then
begin
Stack[Top]:=m;
SumT:=SumT-A[m];m:=m-1;
end
else
begin
Top:=Top-1;
SumT:=SumT+A[Stack[Top]];
Stack[Top]:=Stack[Top]-1;
SumT:=SumT-A[Stack[Top]];
m:=Stack[Top]-1;
end;
end;
end;
end;

Алгоритмы рюкзака
Вот это я и говорил, в случае не сильно отличающихся размеров решение искать сложнее.

Rius
Ну да .... енто факт
Да ладно, попробую на выходных тот код, который я написал ... посмотрим, може заработает

Перебор всех вариантов -> Переборные алгоритмы

Knapsack problem:

To all
Стало быть прогу написал .... если кому надо, то принесу из дома и выложу

выкладывай конечно если не жалко

Ray Adams
Завтра постараюсь принести ... а сделал так и только так (как бы писалось только для себя).
В указанной директории ищуться все директории (все внутренности директории находяться рекурсивно). А потом стало быть работает алгоритм поиска оптимальных директорий для записи, а потом выдается окошка с самими директориями. Прога не осуществляет перенос файл по каким-то директриям, она просто осуществляет свое предложение, как оптимальнее всего писать.

Вопрос такой - исходники нуны или нет?! Сразу скажу - мне их не жалко, тем паче сразу можно будет посмотреть как написана прога. Алгоритм не оптимизирован, но на моей домашней машине после нажатия на кнопку поиск сразу выдает результат (192 директории с фильмами). Точность проверял, вроде все правильно. По крайней мере в директории с 192 директориями вложенными точность составляет 0 байт (болванка забита под завязку), в другой директории (28 директорий) точность составила 897020 (ну ровно столько составила разница от максимального размера болванки).

Писал как-то прогу для оптимальной раскройки рулона на прямоугольные куски. Выяснилось, что по этой теме чуваки защищали диссертации, писали статьи в научные журналы...А мне за две недели сделать, ага %)

synapse
Ну я когда давно еще в технаре учился, одному челу на курсовом примерно такая же задачка попалась, только там не прямоугольные куски, а ЛЮБЫЕ ..... ну ничего ... за месяц сварганили прогу ..... причем варганила вся группа, так как парню можно сказать не повезло

synapse
Мы тогда справились, правда система работала больше часа для достаточно большого полотна ...... ну правда разумеется иногда были фичи специфичные и глюки ... самое главное, что при защите курсового у парня просто не вылезли глюки

Добавлено спустя 34 минуты, 53 секунды:
To All
http://cp.people.overclockers.ru/cgi-bi ... lcDVDR.zip - сама прога
http://cp.people.overclockers.ru/cgi-bi ... source.zip - исходники ее же

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