Pular para o conteúdo
</> Entendendo Algoritmos

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ão
    1 kg · R$ 1.500
  • Som
    4 kg · R$ 3.000
  • Notebook
    3 kg · R$ 2.000