Algoritmus pre hľadanie najlepších dvojíc - algoritmus, pár

Ja som vytiahol túto otázku z algoritmu z myšlienky, o ktorej sa diskutovalo na fóre v januári 2012. Tu vidíte podrobnosti: http://caribbeanopendata.ideascale.com/a/dtd/Underserved-Community-Internet-Access-Baskets-for-BWA-Licensees/85150-16663

Ja som to zarámoval takto:

Blok je definovaný ako oblasť, ktorá má hodnotu v a populáciu veľkosť, str. Košík b je definovaný ako pár blokov.

Vzhľadom na 12 blokov nájdite najlepšiu distribúciu dvojic - založenú na hodnote - týchto blokov do košov.

UPRAVIŤ: Najlepší pár nesmie byť výrazne lepšíako najhorší pár. To znamená, že to, čo sa hľadá, nie je len najlepším priemerom, ale najlepšie rozloženie hodnoty (celková plocha / celkový počet domácností).

Aký algoritmus by som mal vyriešiť, aby som túto otázku vyriešil

odpovede:

Môžete použiť algoritmus Edmonds Blossom V na nájdeniemaximálna zhoda. Tento algoritmus sa používa aj v žiadostiach o prácu. Keď máte 100 pracovníkov a 100 pracovných ponúk, čo najlepšie zodpovedá, keď pracovník má viac ako 1 zručnosť. Zvyčajne je najlepšie zhodné, keď môžete aplikovať nejakú inú logiku, potom len lexikografické triedenie.