O problema da mochila é um dos 21 problemas
NP-completos de
Richard Karp, exposto em
1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é a base do primeiro
algoritmo de chave pública (chaves assimétricas).