Programação dinâmica: roteiro em Londres
O outro exemplo de programação dinâmica do capítulo 9: você tem poucos dias em Londres e muitas atrações. Cada uma leva um tempo e tem uma nota. Quais visitar para somar a maior nota? É a mesma mochila de antes, com tempo no lugar de peso e nota no lugar de valor. Você não pode visitar metade de uma atração, e é por isso que a tabela só usa números inteiros de meios dias.
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];
}- Abadia de Westminster0,5 dias · nota 7
- Globe Theater0,5 dias · nota 6
- Galeria Nacional1 dia · nota 9
- Museu Britânico2 dias · nota 9
- Catedral de St. Paul0,5 dias · nota 8