Dnia Mon, 20 May 2013 12:32:45 +0200 po głębokim namyśle Michal Kleczek
rzekł:

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

> Problem plecakowy? NP-trudny.

Problem plecakowy nie dotyczy jednakowych przemiotów; tu mamy stały
kształt. Rozwiązaniom geometrycznym Bartka muszę się jeszcze przyjrzeć,
ale to mi wcale nie wygląda na problem plecakowy.

--
Edek