W dniu niedziela, 19 maja 2013 17:51:02 UTC+2 użytkownik Edek napisał:

> 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?).


Ktoś kiedyś szukał dobrego programu do rozwiązywania jednej z
wielu odmiany tego zadania. Mianowicie było dostępnych N
kształtów/rozmiarów desek. Zakup każdego kształtu wiązał się
z kosztem. Było także zadanych M kształtów i każdy kształt
potrzebny w określonej ilości. I jedne i drugie kształty
były wielokątami. Trzeba było uzyskać te M kształtów z
tamtych N kształtów, minimalizując koszt całkowity. Na koszt
całkowity poza zakupem N kształtów składał się także koszt
cięcia. Tak więc trzeba było zminimalizować cenę zakupu plus
łączną długość cięcia plus ilość pojedynczych cięć po prostej.

Zadanie było jak najbardziej praktyczne.

Pozdrawiam