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
Najpierw pobierz i zainstaluj LINQPad .
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.
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";.
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.