Empacotando o número máximo de retângulos possíveis

Na seção anterior descrevemos uma estratégia para responder a questão se é possível empacotar $k$ retângulos em uma região convexa ou não. Para empacotar o número máximo de retângulos possíveis, vamos fazer o seguinte.

Começamos tentando empacotar apenas um retângulo e perguntamos para o problema de decisão se é possível ou não. Enquanto a resposta é SIM, tentamos com mais um retângulo. Se a resposta é NÃO, paramos. O fluxograma da Figura mostra esse esquema. Na figura, $n$ é o número de retângulos que foi possível empacotar. Note que não é necessário começar tentando empacotar um retângulo se é conhecido que a resposta para o problema de decisão, digamos, $k=k$ é SIM. Nesses casos, basta começar de $k+1$.

Figure: Esquema geral para o empacotamento de retângulos.