Skocz do zawartości

Zarchiwizowany

Ten temat jest archiwizowany i nie można dodawać nowych odpowiedzi.

Khalim

Algorytm - podział odcinka, minimalizacja odpadu.

Polecane posty

Witam!

Cierpię ostatnimi czasy na totalne matematyczne zaćmienie i nie potrafię wymyślić nic zgrabnego dla następującego problemu.

Otóż sprawa wygląda tak:

Posiadam odcinek o danej długości a,

muszę go podzielić z tym, że "odkrawać" mogę jedynie odcinki o długości b i c.

Cały problem sprowadza się do tego, aby po odcięciu x odcinków "b" i y odcinków "c" otrzymać jak najmniejszy odpad d.

x*b + y*c + d = a

Jakieś pomysły lub nazwa algorytmu, który mógłbym wykorzystać?

Link do komentarza
Udostępnij na innych stronach

Może coś takiego: sprawdzasz ile maksymalnie odcinków b mieści się w a i jakie jest d. Jeśli d = 0, to masz b, a c = 0. Jeśli d != 0, to w pętli zmniejszałbym ilość odcinków b o 1 i dokładał maksymalną ilość odcinków c. Jednocześnie śledzisz (zapamiętujesz) kombinację b i c, dla której d jest najmniejsze. Jeśli w pewnym momencie trafisz na d = 0, to znów masz odpowiedź, ile wziąć odcinków b oraz c. Jeśli dojdziesz do momentu gdy b = 0 i nie uzyskasz d = 0, to po prostu bierzesz zapamiętaną kombinację, dla jakiego zestawu b i c miałeś najmniejsze d.

Link do komentarza
Udostępnij na innych stronach

Wygląda jak problem plecakowy w dosyć mocno uproszczonej formie. Na pewno da się to zrobić brute forcem, ale pewnie da się też rozwiązać to nieco szybciej. Poszukaj informacji o problemie plecakowym (discrete knapsack problem) i być może znajdziesz coś prostszego i szybszego.

Link do komentarza
Udostępnij na innych stronach



  • Kto przegląda   0 użytkowników

    • Brak zalogowanych użytkowników przeglądających tę stronę.
×
×
  • Utwórz nowe...