Wątek: Optytmalne dzielenie odcinków

Witam wszystkich, dawno Was tu nie odwiedzałem ale czasami jak widać trzeba :P


Potrzebuję pomocy a dokładniej jakiegoś nakierowania na rozwiązanie problemu, głowię się nad tym i nie mogę wymyślić żadnego odpowiedniego rozwiązania...


Potrzebuję systemu, który będzie miał za zadanie optymalne podzielenie odcinków, na inne mniejsze odcinki, tak aby pozostały kawałek był jak najmniejszy.

Dokładniej, mam odcinki 600cm i z nich muszę jak najbardziej optymalnie wyciąć mniejsze odcinki, mogą one być różnych długości itp. tak aby niewykorzystany, pozostały fragment pozostały z tego dużego odcinka był jak najmniejszy.

Bąbelkowo nie będzie optymalnie...
Myślałem o obliczeniu każdej możliwości i porównania sumy (do wyniku mniejszego od 600) tak aby wybrać najmniejszą resztę, to dawałoby optymalne ułożenie dla pierwszego odcinka i następnie wykonanie tego samego dla tablicy mniejszych odcinków, z której wycinamy te wyniki które wybraliśmy przed chwilą i tak z każdym kolejnym odcinkiem dużym, aż skończą się te mniejsze...
Jednak taka metoda byłaby strasznie ciężka dla serwera...

Czy ktoś z Was ma może jakąś lepszą wizję na wykonanie tego, lub chociaż jakieś rady, coś aby mnie nakierować w dobrą stronę?


Przepraszam jeśli coś jest ciężkie do zrozumienia lub jeśli wybrałem zły dział.
Pozdrawiam i z góry dziękuję za pomoc!

Zainteresuj się problemem plecakowym oraz problemem wydawania reszty

o widzisz, dzięki Ci bardzo!

RivFox (chyba dobrze pisze) mnie do Ciebie odsyłał ale uznałem, że grzeczniej będzie napisać na forum

Nie jestem pewny czy teraz napiszę prawdę ponieważ nie mam czasu dzisiaj dokładniej się w tym zagłębić jednak po chwili namysłu,
chyba nie do końca o to mi chodziło,
problem plecakowy jest przystosowany do dobierania przedmiotów o największej wartości a mi chodzi tylko o rozmiar...
Problem wydawania reszty nie jest dobrym rozwiązaniem mojego problemu ponieważ jest niedokładny...

Wez napisz dokladniej o co ci chodzi bo sam niebardzo rozumiem. Piszesz o odcinku a nie wiem nawet czym jest odcinek. Jakies przyklady?

dokładniej to jest firma budowlana, dostają parapety w odcinkach po 6metrów i z tego wycinają odpowiednie fragmenty pod okna i potrzebują skryptu, który będzie wybierał najlepiej te parapety z jednego dużego, ponieważ ten kawałem, który zostaje i ma np. metr jest już zazwyczaj do wyrzucenia, dlatego chcą aby zostawało jak najmniej.

Dokładniej, mam odcinki 600cm i z nich muszę jak najbardziej optymalnie wyciąć mniejsze odcinki, mogą one być różnych długości itp. tak aby niewykorzystany, pozostały fragment pozostały z tego dużego odcinka był jak najmniejszy.

Czyli ze zbioru zamówionych długości na parapety trzeba wybrać takie, których suma będzie jak najbardziej zbliżona i mniejsza od 6 metrów, dobrze rozumiem?

Na pewno jest do tego jakiś algorytm, ale nie znam/nie pamiętam go.

Jak dużo jest tych parapetów? Może brutalne rozwiązanie przejdzie w tym przypadku? Po prostu symulujesz wszystkie możliwe podziały (nawet te nieprawidłowe) i wybierasz ten o najmniejszej wadze (najmniejszej ilości zmarnowanego materiału). Dla nieprawidłowego podziału (np. długość kawałków wyciętych z jednej blachy przekracza długość tej blachy) wartość wynosi nieskończoność (max wartość int'a). I po problemie.

Jeżeli rozmiar problemu będzie duży, to wtedy trzeba faktycznie zastanowić się nad optymalnym rozwiązaniem. Nie wydaje mi się jednak, żeby to była tak duża firma, że ma ponad 100 parapetów do wycięcia na jeden raz..

Aravorn dobrze podpowiedzial. Idealnie pasuje to do problemu plecakowego moim zdaniem.

ogólnie tych parapetów ma być 20, do 30.

Co do problemu plecakowego, ja tu nie mam żadnej wartości, każdy parapet ma tą samą wartość, a właściwie to wartość parapetu to jego wielkość... czyli będą jakby dwie takie same tablice.
Problem wydawania reszty nie robi tego optymalnie, po prostu ustala co się może zmieścić ale nie ustawia tego optymalnie...