Já que trabalharemos apenas com quantidades primas de números, vamos computar previamente todos os primos até $$10^4$$ (Limite da questão) utilizando um crivo de Erastóstenes. Então, com todos os primos já computados podemos reduzir o problema ao problema da mochila.
Portanto, basta testar, utilizando programação dinâmica colocar quantidades primas de cada objeto e, após comprar todos os objetos, checar se gasto uma quantidade prima de dinheiro. Código para melhor entendimento:
https://gist.github.com/lawrencefmm/1b4786ddc2992d1ed1d876042888a01f
Deixe um comentário