Problema cu fotbal( e orijinala ;) )

[•yonatan]

liga a 4-a de fotbal din Dardania are N serii in care joaca cate M echipe de fotbal. stiind ca  in liga a 4-a cluburile au foarte putini bani ca sa se duca de la un capat la altul al tarii si ca banii in general ii obtin de la sponsori locali care nu au filiale  peste tot in tara si sunt interesati in general de suprematia  in zona respectiva si nu de suprematia nationala in domeniul lor de activitate, seful ligii MITICA Dardanir a venit cu idee de a pune in fiecare serie echipe cat mai apropiate unele de altele astfel incat cluburile sa nu aiba pierderi prea mari( fotbalul e o gaura fara fund  totushi ) si sa poata atrage cat mai multi sponsori. Planul sau este ca suma sumelor distantelor dintre oricare doua cluburi din fiecare serie (in parte) sa fie minima.
gasiti impartirea optima a acestor cluburi
se dau: N M  pozitiile fiecarui club in sistemul de coordonate xOy(coordonatele de pe pozitia i+2 corespund clubului cu indicele i)
se cere pe n linii diferite cate m echipe reprezentate prin indicii asa cum scrie mai sus

NU STIU DACA ACEASTA PROBLEMA ESTE NEDETERMINIST POLINOMIALA SAU SE POATE REDUCE LA O PROBLEMA CLASICA PE GRAFURI PUR SI SIMPLU MI-AM PUS ACEASTA PROBLEMA IN LEGATURA CU CUM SE IMPART ECHIPELE DE FOTBAL IN SERII IN LIGILE INFERIOARE.
MULTUMESC ANTICIPAT PRIMUL CARE DA REZOLVAREA OPTIMA !

[•sima_cotizo]

Primesti deci N*M perechi de coordonate si vrei sa obtii N multimi cu cate M elemente, astfel incat suma totala a distantelor de la fiecare la fiecare element luat pt fiecare multime sa fie minim? (puteai sa sari peste "poveste" )

[•yonatan]

Primesti deci N*M perechi de coordonate si vrei sa obtii N multimi cu cate M elemente, astfel incat suma totala a distantelor de la fiecare la fiecare element luat pt fiecare multime sa fie minim? (puteai sa sari peste "poveste" )

pai nu e chiar poveste, chiar de la fotbal mi-am pus intrebarea asta adica  sa zicem ca vin in liga a 2-a din liga 1 : ceahlaul, poli iasi, otelul galati(care teoretic ar merge in seria de est a ligii a 2-a si pandurii targu jiu care e teoretic in divizia de vest si ar veni seria de est 19 echipe si cea de vest cu 17. atunci trebuie pusa fc arges de exemplu din seria a2-a in seria 1 si vom avea echilibru  
Dar da asa e  practic trebuie sa faci N grafuri complete a cate M noduri fiecare si pentru fiecare graf faci suma distantelor si aduni la suma totala care trebuie sa fie minima dar cum faci asta :
- programare dinamica sau
- backtacking in caz ca e Nedeterminist Polinomiala?
- greedy desi nu prea imi vine sa cred pentru ca nu mi se pare ca acopera toate solutiile

[•Florian]

Primesti deci N*M perechi de coordonate si vrei sa obtii N multimi cu cate M elemente, astfel incat suma totala a distantelor de la fiecare la fiecare element luat pt fiecare multime sa fie minim? (puteai sa sari peste "poveste" )

pai nu e chiar poveste, chiar de la fotbal mi-am pus intrebarea asta adica  sa zicem ca vin in liga a 2-a din liga 1 : ceahlaul, poli iasi, otelul galati(care teoretic ar merge in seria de est a ligii a 2-a si pandurii targu jiu care e teoretic in divizia de vest si ar veni seria de est 19 echipe si cea de vest cu 17. atunci trebuie pusa fc arges de exemplu din seria a2-a in seria 1 si vom avea echilibru  
Dar da asa e  practic trebuie sa faci N grafuri complete a cate M noduri fiecare si pentru fiecare graf faci suma distantelor si aduni la suma totala care trebuie sa fie minima dar cum faci asta :
- programare dinamica sau
- backtacking in caz ca e Nedeterminist Polinomiala?
- greedy desi nu prea imi vine sa cred pentru ca nu mi se pare ca acopera toate solutiile

Cu alte cuvinte: "Da, asta cer."