Narzędzie do optymalnej dystrybucji plików na wiele płyt DVD?

Mam kilka plików multimedialnych, które chcę nagrać na dysk DVD, ale ponieważ każdy dysk DVD mieści tylko 4,5 GB, muszę znaleźć optymalny sposób uporządkowania plików w celu użycia minimalnej liczby dysków DVD (w przeciwnym razie puste miejsce w każdym z nich DVD można łatwo dodać). Czy są jakieś narzędzia, które mogą w tym pomóc?

Wiele lat temu narzędzie DOS służyło do tego w przypadku dyskietek.

Wypróbuj darmowy DVD Span :

DVD Span to narzędzie do tworzenia kopii zapasowych do zapisywania zawartości dużych folderów na wielu dyskach DVD. DVD Span może automatycznie określić najlepszą organizację każdego dysku, aby zmieścić maksymalną ilość danych na minimalnej liczbie dysków. DVDSpan to doskonałe narzędzie do tworzenia kopii zapasowych kolekcji muzyki, zdjęć, a nawet całego dysku twardego na dyskach DVD. Ponieważ produkuje zwykłe dyski DVD (lub CD), nie jest wymagane żadne specjalne oprogramowanie do odczytu lub przywracania kopii zapasowych.

Ach, problem z plecakiem . Tutaj mogłem znaleźć tylko jeden solver online . Twój rozmiar plecaka wynosiłby 4,5 GB, a każdy pakiet byłby twoimi rozmiarami plików. Będziesz musiał trochę masować jego moc wyjściową, aby dopasować ją do konkretnego zastosowania, ale powinna być wykonalna. Nie będzie to jednak działać bardzo szybko, ponieważ ten problem jest trudny .

Przegląd

Odpowiedź Jeffa Shattocka jest prawidłowa, ponieważ jest to równoważne (lub izomorficzne, jak piszą matematyki) z kombinatoryjnym problemem optymalizacji, ale jest równoważne z problemem jednowymiarowego pakowania bin , a nie problemem plecaka .

Na szczęście dla ciebie, mam trochę kodu, który rozwiąże ten problem dla ciebie lub kogokolwiek innego, z dostępem do komputera z systemem Windows z zainstalowaną co najmniej wersją 3.5 .NET Framework.

Trudne rozwiązanie

1. Najpierw pobierz i zainstaluj LINQPad .

2. Po drugie, pobierz zapytanie LINQPad, które właśnie napisałem - oto linq (ha) do surowego pliku. Zapisz go jako plik .linq i otwórz go w LINQPad.

3. Zmień parametry:

   Oto część kodu zapytania LINQPad, którą należy zmienić:

   int binSizeMb = 4476; // This is the (floor of the) total size of a DVD+R reported by CDBurnerXP. string rootFileFolderPath = @"F:\2006 - Polyester Pimpstrap Intergalactic Extravaganza multicam";

   Zmień binSizeMbrozmiar swojego „bin”, np. CD, DVD, np. int binSizeMb = 650;na CD.

   Uwaga - binSizeMbwartość jest interpretowana jako coś, co jest czasami nazywane mebibajtem . W przeciwieństwie do mojego dzieciństwa, kiedy wszystkie wielokrotności bajtów były „binarne”, czasami „MB” odnosi się teraz do „dziesiętnego megabajta” lub dokładnie 1 000 000 bajtów, w przeciwieństwie do 1 048 576 bajtów mebibajta (MiB), który jest używany w moim kodzie . Jeśli chcesz to zmienić, zmień wiersz const int bytesPerMb = 1048576;w kodzie na const int bytesPerMb = 1000000;.

   Przejdź rootFileFolderPathdo pełnej ścieżki do folderu zawierającego pliki, które chcesz „spakować do pojemników”, np. string rootFileFolderPath = @"C:\MySecretBinFilesFolder";.

4. Uruchom zapytanie, naciskając F5lub klikając przycisk Wykonaj w lewym górnym rogu zakładki zapytania.

Wyniki

Kod zapytania wyliczy rootFileFolderPathrekurencyjnie wszystkie pliki w folderze, co oznacza, że ​​obejmie pliki również we wszystkich podfolderach.

Następnie utworzy „pojemniki” dla plików, tak aby całkowity rozmiar wszystkich plików w każdym pojemniku był mniejszy lub równy podanemu rozmiarowi pojemnika.

W okienku wyników LINQPad zobaczysz dwie listy.

Pierwsza lista zawiera wszystkie znalezione pliki, wymienione w kolejności malejącej według rozmiaru.

Druga lista to pojemniki utworzone przez „pakowanie plików” wraz z listą plików i ich rozmiarami, a także pozostałym rozmiarem pojemnika.

Oto zrzut ekranu pokazujący drugą listę i dwa pierwsze utworzone pojemniki:

Analiza kursowa

Według Wikipedii zastosowany przeze mnie algorytm - strategia First Fit Dec zmniejszenie (FFD) - nie powinien być taki zły; Wikipedia stwierdza:

W 2007 roku udowodniono, że związane 11/9 OPT + 6/9 dla FFD jest ciasne.

„OPT” odnosi się do strategii optymalnej (jako coś potencjalnie nieosiągalnego, a nie jakakolwiek konkretna strategia).

Opierając się na moich nieco rozmytych wspomnieniach dotyczących matematycznych terminów, powinno to oznaczać, że strategia FFD powinna, w najgorszym przypadku, spakować przedmioty do ~ 1,22 razy więcej pojemników niż optymalna strategia. Tak więc strategia ta może spakować przedmioty do 5 pojemników zamiast 4. Podejrzewam, że ich wydajność prawdopodobnie będzie bardzo zbliżona do optymalnej, z wyjątkiem określonych „patologicznych” rozmiarów przedmiotów.

Ten sam artykuł w Wikipedii stwierdza również, że istnieje „dokładny algorytm” . Mogę też zdecydować się to wdrożyć. Będę musiał najpierw przeczytać artykuł opisujący algorytm.

Myślę, że możesz użyć dowolnego narzędzia do kompresji, które pozwala na dzielenie archiwum

Możesz wziąć jeden z wariantów programu w przewodniku Autostopowicza po Haskell , być może po przejrzeniu części tego samouczka; samouczek jest napisany wokół rozwiązania dokładnie twojego problemu polegającego na dystrybucji rzeczy na kilka dysków, dzięki czemu rozwiązanie jest stopniowo udoskonalane, czego przykładem jest następujący fragment z rozdziału 3 samouczka:

Już wystarczająco dużo wstępnych kwalifikacji. chodźmy spakować trochę płyt CD.

Jak już zapewne zauważyliście, nasz problem jest klasyczny. Nazywa się to „problemem plecakowym” ( google go w górę , jeśli jeszcze nie wiesz, co to jest. Istnieje ponad 100000 linków).

zacznijmy od chciwego rozwiązania ...

Więcej pomysłów: powiązane pytanie

Oto podobne pytanie (choć nie to samo: nie jest poproszony o optymalizację), w którym możesz znaleźć bardziej przydatne rozwiązania / programy do swojego zadania (jeśli zostaną opublikowane):

• https://unix.stackexchange.com/q/10158/4319 - „Dzielenie dużego drzewa katalogów na fragmenty o określonym rozmiarze?”

Kilka wskazówek dotyczących zrozumienia programowania w sugerowanym samouczku

Ogólnie rzecz biorąc, kod Haskell jest dość ekspresyjny (ponieważ Haskell jest językiem programowania na wysokim poziomie abstrakcji), a zatem może być łatwo zrozumiany.

Patrząc na kod jednego z rozwiązań, pamiętaj, że struktura najwyższego poziomu programu, który chcemy napisać, jest dość prosta, jak opisano w rozdziale 1 samouczka:

Zastanówmy się teraz przez chwilę, jak nasz program będzie działał, i wyrażmy to w pseudokodzie:

main = Read list of directories and their sizes.
       Decide how to fit them on CD-Rs.
       Print solution.

Brzmi rozsądnie? Tak myślałem.

Uprośćmy trochę nasze życie i załóżmy na razie, że obliczymy rozmiary katalogów gdzieś poza naszym programem (na przykład za pomocą „ du -sb *”) i odczytamy te informacje ze standardowego wejścia.

i przyjrzyj się bliżej częściom rozwiązania.

Wiele lat temu napisałem skrypt PHP, aby wykonać takie zadanie: https://bitbucket.org/borszczuk/php-backup-maker/

Spróbuj także Discfit, który wybiera pliki i katalogi do skopiowania na różne dyski:

https://sourceforge.net/projects/discfit/