Programação dinâmica
Resolve um problema grande combinando respostas de subproblemas menores, guardadas em uma tabela. Exemplo: o problema da mochila — qual conjunto de itens cabe e vale mais?
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
function mochila(itens, capacidade) {
// tabela[i][c - 1]: melhor valor usando os itens 0..i com capacidade c
const tabela = itens.map(() => Array(capacidade).fill(0));
for (let i = 0; i < itens.length; i++) {
const { peso, valor } = itens[i];
for (let c = 1; c <= capacidade; c++) {
const sem = i > 0 ? tabela[i - 1][c - 1] : 0; // linha de cima: sem o item
const sobra = c - peso;
let com = 0; // com o item (se couber)
if (sobra >= 0) {
com = valor + (i > 0 && sobra > 0 ? tabela[i - 1][sobra - 1] : 0);
}
tabela[i][c - 1] = Math.max(sem, com);
}
}
return tabela[itens.length - 1][capacidade - 1];
}Capacidade de 4 kg. Qual combinação vale mais?
- Violão1 kg · R$ 1.500
- Som4 kg · R$ 3.000
- Notebook3 kg · R$ 2.000