[Tetriando]

Algorytm pierogowy

Ostatnio podczas przygotować do Wigilii zauważyłem, że zwykle z kawałka ciasta wycina się szklanką jednakowe kółka w sposób raczej na oko. Czy istnieje jakiś algorytm który zapewniłby mi, że z takiej serii wycinania kół zostanie jak najmniej ciasta?

Pozdrawiam :D

#algorytmy #programowanie #informatyka #problem #pierogi

[Lrrr]

@Tetriando: UWAGA DAJE PROTIPA TO CIASTO MOŻESZ WYKORZYSTAĆ PONOWNIE WYSTARCZY JE ROZWAŁKOWAĆ JESZCZE RAZ

[G.....t]

@Lrrr: k---a ale skisłę XD

[ntskj]

@Tetriando: klasyczny algorytm plecakowy powinien chyba dać radę, kwestia reprezentacji ciasta w pamięci

[Tetriando]

@Lrrr: Wiem, ale chcę te ponowne wykorzystania zminimalizować

[G.....t]

@Tetriando: wciśnij ciasto do szklanki, rozbij szklanke, wyciągnij walec z ciasta i potnij tasakiem

[Tetriando]

@Godlike_Atheist: Załóżmy, że mamy do dyspozycji tylko jedną szklankę o wysokości 1 plastra pierogowego xD

[k.....r]

@Tetriando: http://en.wikipedia.org/wiki/Packing_problem#Circles_in_square

[Tetriando]

@kuhar: No, coś konkretnego :D Nie zapominajmy jednak, że ciasto ma nieregularny kształt, co znacząco wpływa na złożoność problemu :D

[Tetriando]

@kuhar: Np tutaj chcę wyciąć koła o zadanym r

Ciasto można reprezentować np jako wielokąt o pewnej dokładności.

I co dalej, bruteforce to jedyna rada?

[k.....r]

@Tetriando: powodzenia z bruteforcem, kiedy przestrzen nie jest dyskretna

to jest problem np-trudny

[GalAn89]

@Tetriando: A może algorytm ewolucyjny?

[jgoluch]

@Tetriando: Najlepszy tutaj będzie SIMPLEX.