Dia 60/2019 - Algoritmos em JS: Técnicas de Design

Desafio #92daysofcode que fiz no final de 2019. Nesse artigo temos o dia 60, mostrando o uso de algoritmos de técnicas de design.

Veja abaixo uma lista de várias abordagens populares:

Código

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// https://en.wikipedia.org/wiki/Knapsack_problem
// https://pt.wikipedia.org/wiki/Problema_da_mochila
// the knapsack problem - dynamic programming
const knapsack = (itemsNumber, capacity, weights, values) => {

if(itemsNumber === 0 || capacity === 0) {
return 0;
}

if(weights[itemsNumber - 1] > capacity) {
return knapsack(itemsNumber - 1, capacity, weights, values);
}

const dontPutInKnapsack = knapsack(itemsNumber - 1, capacity, weights, values);
const putInSack = values[itemsNumber - 1] + knapsack(itemsNumber - 1, capacity - weights[itemsNumber - 1], weights, values);

return Math.max(dontPutInKnapsack, putInSack);
}

const itemWeights = [2, 3, 6];
const itemValues = [3, 6, 9];
const numberOfItemsToConsider = 10;
const totalNumberOfItems = 3;

const maximizeTotal = knapsack(totalNumberOfItems, numberOfItemsToConsider, itemWeights, itemValues);
console.log(maximizeTotal);
// 15

Conclusão

A postagem original pode ser vista no meu Instagram e o código está acessível no meu Github.

Relacionados

Ao fechar este aviso ou continuar navegando no site Nerd Calistênico, você aceita o uso de cookies.

Este site usa cookies para assegurar a melhor experiência para os nossos usuários. Consulte nossa política de privacidade.

Uma nova versão está disponível. Clique aqui para atualizar.