Pular para o conteúdo
</> Entendendo Algoritmos

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 Westminster
    0,5 dias · nota 7
  • Globe Theater
    0,5 dias · nota 6
  • Galeria Nacional
    1 dia · nota 9
  • Museu Britânico
    2 dias · nota 9
  • Catedral de St. Paul
    0,5 dias · nota 8