Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Оптимальная разбивка файлов
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
zim zim вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 31.10.2005
По умолчанию Оптимальная разбивка файлов - 02.02.2006, 18:33

Описание проблемы:
~~~~~~~~~~~~~~~~~~
Есть папка размером 100 Гб. в ней расположены
файлы, размер которых колеблется от 50 до 4000 Мб. Необходимо
записать эту папку на диски ДВД так, чтобы было использовано
минимум дисков. Ёмкость диска = 4483 Мб.

I.Пример "ручного" метода решения:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Выделяем файлы, подсчитываем их общий размер. Если он более-менее
похож на 4483 мб, то записываем эти файлы на диск.
2) Повторяем шаг 1) до тех пор, пока не останется файлов.
==>Этот метод не даёт минимального избытка дискового пространства...

II.Пример "автоматического" метода решения:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Суммируем размер всех файлов в папке на 100 Гб. Получили размер,
равный 100 Гб. Делим общий размер на размер ДВД-диска.
Получаем "в идеале": 100 Гб / 4483 метра = 22,842 диска
2) Осуществляем перебор суммирования всех возможных вариантов
заполнения диска. Сохраняем результаты.
3) Сравниваем каждый результат с "идеальным значением" и выбираем
наиболее приближенный.
====================================
Это всё в теории. На практике же не совсем понятно, как должен выглядеть
алгоритм для "автоматического решения"(пункт II.2). Может кто-нибудь сталкивался
с подобными задачами или существует готовое ПО?
Ответить с цитированием
  (#2 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 02.02.2006, 18:49

Существует WinRar
В этой ситуации важно, что он может создавать архивы определенного размера (хотя, конечно, где-то полезно и прессовать)
Ответить с цитированием
  (#3 (permalink)) Старый
Huan Huan вне форума
Member
 
Сообщений: 79
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 21.01.2006
По умолчанию 02.02.2006, 20:32

Решал что-то похожее так:

1) Сортируются файлы по размеру (получаем список файлов с убыванием размера)
2) В пустой список добавляется первый (самый большой) файл
3) Далее, если возможно, добавляется второй, если нет, то пытаемся добавить файл еще меньше (следующий в списке)
4) И вот так вот до тех пор пока не наберем необходимый объем
Ответить с цитированием
  (#4 (permalink)) Старый
zim zim вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 31.10.2005
По умолчанию 02.02.2006, 20:41

Цитата:
Originally posted by Huan
[b]Решал что-то похожее так:

1) Сортируются файлы по размеру (получаем список файлов с убыванием размера)
2) В пустой список добавляется первый (самый большой) файл
3) Далее, если возможно, добавляется второй, если нет, то пытаемся добавить файл еще меньше (следующий в списке)
4) И вот так вот до тех пор пока не наберем необходимый объем
этот вариант отпадает. т.к. это эвристический алгоритм, дающий далеко не оптимальное решение. только полным перебором всех вариантов можно добиться наилучшего решения.
Dian:
необходимо обойтись без физического разбиения файла на несколько частей.
---
спасибо за ответы. будут ещё умные мысли?
Ответить с цитированием
  (#5 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 02.02.2006, 20:46

К Винитарху обратись...
Он хвастал, что такую задачу решал (даже болеее сложную) и его прорамма вроде какой то конкурс выиграла.... (Если я ничё не путаю)


импортирован с progz.ru
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 03.02.2006, 16:18

Действительно ли нужно самое оптимальное решение. Метод, который предложен выше, вполне рабочий
Ответить с цитированием
  (#7 (permalink)) Старый
zim zim вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 31.10.2005
По умолчанию 03.02.2006, 16:33

Цитата:
Originally posted by Dian
[b]Действительно ли нужно самое оптимальное решение. Метод, который предложен выше, вполне рабочий
какой именно метод? если метод "обратиться к Винитарху" то я уже обратился. если твой метод(винРар), то он не подходит. Если метод Хуана, то он очень-очень не оптимален. Ладно, как всегда придётся самому мозговать и придумывать полный перебор вариантов
Ответить с цитированием
  (#8 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 03.02.2006, 16:42

Цитата:
Originally posted by zim
[b]Если метод Хуана, то он очень-очень не оптимален
О нем речь и была. Там не так уж много файлов для полного перебора
Ответить с цитированием
  (#9 (permalink)) Старый
Huan Huan вне форума
Member
 
Сообщений: 79
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 21.01.2006
По умолчанию 03.02.2006, 17:40

Это самый простой ИТЕРАТИВНЫЙ метод
Думаю он для домашнего применения вполне,
а применять рекурсию при (100Гб/50Мб = 20 000 файлов)
дело не простое!
Ответить с цитированием
  (#10 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,979
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 06.02.2006, 21:17

Эта обычная задача линейной (одномерной) упаковки.
Смотрите журнал "Информационные технологии" за последние годы. Там одно из отдельных приложений посвящено подробному обзору подобных задач. В нём приведены эвристики. Автор обзора - проф. Мухачёва из Уфимского авиа-института (если мне не изменяет память).
Свои эвристики не дам (по меркантильным соображениям). Полагаю, что Вам хватит опубликованных.
Ответить с цитированием
  (#11 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 06.02.2006, 22:06

Здесь обсуждалась эта проблемма:
http://community.livejournal.com/ru_lambda...1086.html?nc=12
Ответить с цитированием
  (#12 (permalink)) Старый
tоkito tоkito вне форума
Member
 
Сообщений: 266
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.07.2005
По умолчанию 07.02.2006, 11:19

учи жадные алгоритмы, например, здесь http://rain.ifmo.ru/cat/view.php/theory/al...sis/greedy-2004, и вперед.

а винитарх жадина, к0да пожалел, думает его тут же за сиксильон баксов продадут китайцам


а чё у тебя за файлы то кстати раз тебе по как их распихивать, уж не то ли что я подумал ?? и размеры подходящии ...
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
zim zim вне форума
Member
 
Сообщений: 28
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 31.10.2005
По умолчанию 07.02.2006, 18:00

спасибо за ответы. буду вникать в тему. а файлики у меня - это аниме мультфильмы
Ответить с цитированием
  (#14 (permalink)) Старый
Mr. Пронька Mr. Пронька вне форума
Member
 
Сообщений: 168
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.06.2005
По умолчанию 07.02.2006, 18:41

"а применять рекурсию при (100Гб/50Мб = 20 000 файлов) дело не простое!"
А ты прикинь, какая глубина рекурсии будет? Вряд ли, большая.
Ещё бы к этим 4-м пунктам добавил следующее. Если файл слишком велик, чтобы уместиться в группу, то добавляем его в следующую.
Ответить с цитированием
  (#15 (permalink)) Старый
tоkito tоkito вне форума
Member
 
Сообщений: 266
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.07.2005
По умолчанию 07.02.2006, 20:55

все таки не порнуха .. жалко

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

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Разбивка списка на уровни Венечка Prolog 3 22.01.2012 05:41
разбивка сплошного текста fukidid Любые вопросы от новичков 1 22.12.2011 04:39
разбивка харда на разделы lantan1990 Любые вопросы от новичков 1 27.05.2011 06:39
разбивка харда Лёха. Накопители 8 28.03.2011 08:45
Разбивка строки S на слова из набора romeo007.06 Prolog 1 11.12.2010 14:50
Разбивка жесткого диска Crypto5 Накопители 0 04.11.2008 01:53
Перехват звука и разбивка на составляющие wenom C++ Builder 0 04.07.2007 17:18
Разбивка на страницы в Word Krasnaja Shapka Visual Basic 0 02.11.2006 14:36
Разбивка по страницам =kolya= PHP 4 13.04.2006 22:19
Палиндром + разбивка текста на предл-ния imported_Pavlik Prolog 4 30.03.2006 18:25
Разбивка файла на поля Просто_Алексей Delphi 1 17.05.2005 08:51
Разбивка вывода по N пунктов. maora PHP 2 12.08.2004 04:30



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов