On 2013-05-19 17:51, Edek wrote:
> Witam, grupa źle na mnie wpływa - nakładając dzisiaj rano
> płaty boczku na patelnię (okrągłą) zastanawiałem się,
> jakiego algorytmu użyć, aby uzyskać możliwie największą
> ilość boczku nałożonego na patelnię tak, żeby się równo
> przypiekł.
>
> Powiedzmy, że boczek jest podłużny i ma przekrój opsiany
> poligonem, jak to boczek. Kroimy w poprzek, czyli w
> płaszczyźnie przekroju, i układamy na patelni o promieniu
> r tak, aby uzyskać najlepsze możliwe wykorzystanie powierzchni
> patelni. Przekrój boczku na płaską podstawę (nie wiem jak
> to dobrze opisać, mam nadzieję że wiadomo o co chodzi,
> z boczkiem każdy przecież miał do czynienia kiedyś, prawda?).
>
> O ile mnie zadanie rano stanowczo przerosło i nawet nie
> oczekuję żadnych konkretnych algorytmicznych rozwiązań,
> jaka jest złożoność tego problemu? Powiedzmy, że boczek
> ma przekrój wypukły.
>

Problem plecakowy? NP-trudny.

--
Michal