Witam wszystkich.


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!

Tak ciężka, że serwer wybuchnie.
Jak sobie przypominam był już taki temat.

Z tego co zrozumiałem, chodzi Ci o coś co ma nazwę problem wydawania reszty

Problem wydawania reszty nie jest odpowiedni, ponieważ nie wybiera najbardziej optymalnej ilości elementów...

Problem plecakowy także jest chyba nieodpowiedni ponieważ ma on z założenia ustalony rozmiar a także wartość elementów a ja nie mam żadnej wartości, jest ona równa wielkości...

Ale zauważ, że właśnie tak musisz zrobić (a przynajmniej mnie się tak wydaje).
Po pierwsze: posortuj tablicę odcinków do wycięcia, będzie łatwiej operować.
A potem w pętli:
1. bierzesz najdłuższy odcinek
2. wyliczasz resztę i próbujesz dopasować najdłuższy odcinek (krótszy od reszty) z pozostałych i robisz to tak długo, aż nie będzie z czego dopasowywać. Notujesz "stratę" i użyte odcinki, dane przydadzą się na potem. No chyba że "strata" wynosi zero, to lepszego wariantu nie znajdziesz.
3. do reszty po pozostałym najdłuższym odcinku bierzesz DRUGI (i w kolejnych iteracjach następne) krótsze odcinki i wykonujesz to co w p.2
4. Jeśli nie miałeś sytuacji, że "strata" wynosi zero, to bierzesz ten wariant, w którym strata była minimalna
5. Wykorzystane odcinki usuwasz z tabeli
6. idziesz do p.1.

Krótka ilustracja (odcinki dobrane tak, by się nic nie zmarnowało, ale załapiesz ideę). Masz do zrobienia odcinki o długościach 420, 350, 170, 130, 80, 50 i wycinasz je z 600cm. Dane są już posortowane.
1. Bierzemy najdłuższy. Mamy reszty 180. Najdłuższy mniejszy od 180 to 170. Zostaje reszta=10
2. Z reszty 180 wybieramy nie najdłuższy, ale drugi najdłuższy. Czyli 130. 420+130 = 550. Reszta=50. Patrzymy na taki, co jest nie dłuższy niż 50 - mamy dokładnie 50. Idealny wariant: 420+130+50.
3. Usuwany dane - w tablicy zostają 350, 170, 80. Próbujemy je dopasować - suma wynosi dokładnie 600 - usuwamy dane.
4. tablica jest pusta - koniec zadania.


Ojejku, a ile ty tych iteracji (odcinków do wycinania) masz? Dziesiątki tysięcy? Myślę, że przy kilkuset żaden komp się nawet nie zająknie - no chyba że algorytm będzie wyjątkowo nieefektywnie napisany.