APA

Problema Subset Sum
Complexidade: Como a tabela tem n+1 linhas e c+1 colunas, o algoritmo consome  Ο(nc)  unidades de tempo, mesmo no pior caso.
Aplicação: O problema dos cheques:  Suponha que p1, p2, … , pn são os valores dos cheques que você emitiu durante o mês. No fim do mês, o banco debita uma quantia c na sua conta.  Você quer saber se algum conjunto de cheques corresponde ao valor debitado.

Referência: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/mochila-subsetsum.html