Algoritmo greedy: differenze tra le versioni

Versione delle 22:29, 6 mar 2019

Versione delle 20:16, 15 set 2020

Riga 7:

Il problema comunemente detto [[Problema del commesso viaggiatore|"del Commesso Viaggiatore"]], cioè "dato un numero di consegne e di ritiri con un mezzo che ha una portata massima P, si organizzi il viaggio che consente di viaggiare il minor numero di km con il maggior carico possibile per ottenere il massimo guadagno", non è un problema risolvibile tramite un algoritmo di tipo greedy, ma solo tramite algoritmi per [[NP-Completo|problemi NP-Completi]].

Il primo esempio è risolvibile grazie ad un algoritmo greedy solo per quell'insiemeopportuni insiemi di valori di monete: infatti se ci fossero ad esempio anche monete da 105 eurocent (valori monete: 105, 100, 10, 1), l'algoritmo greedy darebbe un totale di 8 monete (una da 105 e 7 da 1), mentre la soluzione ottima è quella con 4 monete (100+10+1+1).

== Definizione formale ==