Ccm
Problema se rezolvă utilizând metoda programării dinamice. Stările se vor determina urmând observaţia... Va trebui să cuplăm cele n noduri din mulţimea L cu unele noduri din mulţimea R, reprezentate de biţii de 1 din întregul stare. Fie, astfel, valoarea maximă a cuplajului dintre primele i noduri din L şi nodurile din stare iar câte cuplaje de cardinalitate maximă există.
Recurenţa este:
Considerăm în continuare nodurile din R reţinute de stare ca nodurile actuale din R. Astfel, fie vom cupla primele i – 1 noduri cu nodurile reţinute de stare din R, fie vom încerca să cuplăm nodul i cu unul din nodurile din R actuale vecine cu acesta. Fie j acest nod. Acum ne rămân de cuplat primele i – 1 noduri din L cu nodurile stare – 2j din R.
Valorile matricei se vor actualiza corespunzător în funcţie de valoarea lui .
Complexitate: O(2n * n * m).