Optymalny algorytm cięcia odcinków

0

WItam. Problem jest taki:
Istnieje n odcinków (np. kabla) o różnych długościach. A ja potrzebuję x odcinków też o różnych długościach, Jak wybrać OPTYMALNIE potrzebne mi x odcinków z n odcinków ? Oczywiście mogę sobie ciąć n odcinki lecz nie mogę ich sklejać. Jak wybrać i ew. pociąć n odcinki aby straty (czylki odpady po pociętych odcinkach) były jak najmniejsze.
Mam nadzieję że dosyć jasno wytłumaczyłem problem. Poszukuje po prostu takiego algorytmu. Ważne jest aby liczenie nie trwało zbyt długo, czyli próba wszystkich kombinacji i późniejsza analiza najmniejszych strat odpada.

dzięki, pozdrawiam
Darek W.

0

Widzę tylko jedną możliwość: zrób to dynamicznie. Jako, że jestem leniwy, nie napiszę jak konkretnie (nie chce mi się myśleć) - ale ta metoda wydaje się pasować do problemu.

0

Ja bym się raczej rozejrzał za algorytmami zachłannymi lub genetycznymi. One nie przeglądają całej przestrzeni rozwiązań, ale dają prawie optymalny wynik w znacznie krótszym czasie niż algorytmy wyczerpujące całą przestrzeń rozwiązań.
Jednak nie podam żadnych konkretnych przykładów, gdyż jestem w trakcie sesji i nie mam czasu :-(.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0