подбор группы файлов до заданого размера

[Zeon25]

помогите с задачкой
Есть цифровой ряд и и имена файлов, например:

3171532538 имя
2737784320 имя
2201862144 имя
1576968192 и т.д
1468350464
1468035072
1467871232
1467850752
1370968064
1302675600
1173901312
704047104
652073656

нужно из него выбрать числа на сумму, максимально приближающуюся к заданному числу (<= 8500594688).
Каждое число добавляется только один раз.

Для чего это нужно? Оптимизация файлов (фильмов) под размер болванки DVD-R. Пробовал несколько программ (Ignition, CalcDVDR, NovA Collection Divider, nnbackup228.exe) - во всех примитивный алгоритм подбора - просто берут самый большой файл, вычитают его из размера болванки и ищут наибольший файл меньше этой разности. Всё. Нормальную утилиту так и не нашел

Раньше подбирал руками. На однослойную болванку хорошо ложатся два фильма под 2350000 или три (2,18, 1,5, 700) - один из них должен быть Мб на 200 больше стандарта или три х 1560000.
Сейчас подешевели двухслойные болванки 8500 - их заполнить руками гораздо сложнее.

в итоге хотелось бы получить на выходе
название файлов которые идеально подходят для записи на диск

имя1
имя2
имя3

ну а в идеале автоматом сразу группы файлов

[Serge_Bliznykov]

задача интересная.
Кстати, Вы её уже на рубоарде озвучивали, так?

Несколько вопросов к Вам.
1) если ли допустимая точность (величина приближения). Ну, поясню, например, если сумма отличается от заданной величины меньше чем на Epsilon - то дальше можно не искать решение (хотя, возможно, найденное решение далеко не оптимальное! И не найденные, к примеру, 6 больших фильмов, а 15 маленьких лягут точно в размер!)
Т.е. обязательно ли искать ОПТИМАЛЬНОЕ решение?

2) если ли ограничение на количество обрабатываемых файлов? Т.е. из скольки файлов Вы хотите произвести подбор?

3) Ну, Excel, как я понимаю, абсолютно не обязательное требование? Если это будет утилита, написанная на другом языке программирования, Вам же всё равно?

[Zeon25]

Serge_Bliznykov ответы по порядку
1. Оптимальное решение это и есть моя задача, хотя если первый найденный результат будет будет отличаться от идеального на 100 мб, то можно принять как удовлетворительный. Но все же хотелось бы максимально увеличить КПД. Из-за 100 мб потом возможно придется целый диск портить.

2.ограничения не желательны, предположим это будет 100 файлов, а может и больше.

3. excel конечно не критичен.

Если добавите возможность выбора, как работать с подпапками будет вообще супер. А именно выдирать файлы для анализа из вложенных папок или писать эти папки целиком.

Такой проект на данный момент думаю заинтересует многих в сети.

[motorway]

Не совсем по теме, но, может быть, перейти на DVD-RW?

[Aent]

Господа, не надо изобретать велосипед.
Это популярная на младших курсах математических ВУЗов задача об одномерной оптимальной упаковке.
http://www.wikiznanie.ru/ru-wz/index...B2%D0%BA%D0%B5
Cм так же:
http://www.math.nsc.ru/LBRT/k5/lec12.doc
Или вы соглашаетесь на приближенное решение с полиноминальной сложностью,
или вперёд к полному перебору

[Serge_Bliznykov]

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

А если, скажем, погрешность не 100 Мб, а 1 Мбайт? Или 500 килобайт? Всё равно продолжать перебирать, подыскивая более оптимальный вариант?!!

ограничения не желательны, предположим это будет 100 файлов, а может и больше.

А то, что подбор оптимального варианта при 100 файлах займёт пару лет непрерывного подбора, Вас, разумеется не смущает. я прав?!

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

Такой проект на данный момент думаю заинтересует многих в сети.

Честно говоря, я так не думаю...
Гораздо лучше записать фильмы подходящии друг другу по жанру/содержанию, чем писать на один диск, скажем, мелодраму, голивудский боевик, старый советский детектив, триллер,ужастик и детский мультфильм.. Я для себя эту проблему (хранения видео) пока решил путём покупки специального винта под фильмы. Посчитайте, сколько стоит винт, разделите его стоимость в пересчёте на 8500594688 байт
и сравните со стоимостью одной двухслойной болванки. Конечно, есть свои минусы, но есть и плюсы... Особенно в свете того, что сейчас появлются HD BDRipы, размером больше одной болванки...
Хотя, признаюсь, иногда и на DVD+R пишу фильмы... Т.к. сказать, для упрощения доступа к коллекции.

Короче, я постараюсь сделать рабочий вариант.
Как-то давненько (год назад) тут, на форуме, гениальный программист LeBron выложил свой вариант программки, решающей эту задачу. Вот на основе этого кода я могу написать утилиту. (ну, фактически использовав его код, как вычислительное ядро этой утилиты). Надеюсь, что LeBron не будет против.

[vikttur]

На Планете слэн выкладывал решение:
http://www.planetaexcel.ru/forum.php?thread_id=10417

[Zeon25]

vikttur я все же надеюсь на Serge_Bliznykov так как решения предложенные тобой не работают так как хотелось бы. Но за решение спасибо

[Zeon25]

Serge_Bliznykov, надеюсь у тебя получится написать рабочий вариант, так как мои 2 терабайтных hdd уже не способны меня удовлетворить, фильмы на них льются постоянно, а в коллекции некоторые оставить хочется. Да и дать посмотреть людям так можно, не давать же им мой hdd? денег не хватит а представь hdd накроется что тогда? я же умру от горя.

Во общем на тебя и местных гуру вся надежда.

[Serge_Bliznykov]

Zeon25,
ну давайте попробуем что-то сваять

в пост #6 я задал несколько вопросов. Ответьте на них, пожалуйста...