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, bst[i][stare] valoarea maximă a cuplajului dintre primele i noduri din L şi nodurile din stare iar ccm[i][stare] câte cuplaje de cardinalitate maximă există.
Recurenţa este:
ccm[i][stare] = ccm[i - 1][stare] + \displaystyle\sum_{j \in V(i)}\ {ccm[i-1][stare-2^j]}
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 ccm[i][stare] se vor actualiza corespunzător în funcţie de valoarea lui bst[i][stare].
Complexitate: O(2n * n * m).