El problema de la mochila algorítmica (y su implementación en Python) es interesante y es parte del primer programa informático y digital.
Este problema ilustra algoritmos codiciosos que enumeran todas las posibilidades de resolver un problema para encontrar la mejor solución.
El problema de la mochila del algoritmo de Python es un problema de optimización, es decir, una función que debe maximizarse o minimizarse y restricciones que deben cumplirse.
El problema de la mochila : algoritmo de Python
Para una mochila con capacidad máxima de artículos P y N, cada uno con su propio peso y un valor establecido, deseche los artículos dentro de la mochila para que el contenido final tenga el valor máximo.
Declaración de muestra:
- Capacidad máxima de la mochila: 11 unidades
- Número de artículos: 5
- Valores de los artículos: {10,50,20,30,60}
¿Cuál es el valor máximo que se puede poner en la mochila considerando la restricción de capacidad máxima de la bolsa que es 11?
Algoritmo codicioso python
Una solución eficaz es utilizar un algoritmo codicioso. La idea es calcular la relación valor / peso de cada objeto y clasificar el objeto en función de esta relación calculada.
Tomamos el objeto con la proporción más alta y lo agregamos hasta que no podamos agregar más.
En versión fraccionada es posible agregar fracciones de artículo a la mochila.
Implementación del problema de la mochila Python: versión no fraccionada
Aquí hay una implementación del problema de la mochila python en versión no fraccionada, es decir que no se puede agregar una fracción de un objeto en la bolsa. Solo se pueden agregar objetos completos.
clase BagObject:
def __init __ (self, weight, value, index):
self.index = índice
self.weight = peso
self.value = valor
self.report = valor // peso
#Función para la comparación entre dos BagObjects
# Comparamos el ratio calculado para ordenarlos
def __lt __ (yo, otro):
volver self.report & lt; otro.informe
def getMaxValue (peso, valores, capacidad):
arraySort = []
para i en rango (len (peso)):
arraySort.append (BagObject (peso [i], valores [i], i))
#Ordena los elementos de la bolsa por su informe
arraySort.sort (reverse = True)
counterValue = 0
para el objeto en arraySort:
currentWeight = int (object.weight)
currentValue = int (object.value)
si capacidad - peso actual> = 0:
# agregamos el objeto en la bolsa
# Restamos la capacidad
capacidad - = peso actual
counterValue + = currentValue
# Agregamos el valor en la bolsa
return counterValue
peso = [1,5,3,2,4]
valores = [10,50,20,30,60]
capacidad = 11
maxValue = getMaxValue (peso, valores, capacidad)
print ("Valor máximo en la mochila =", maxValue)
El resultado es el siguiente:
py sacados.py Valor máximo en la mochila = 120
Implementación del problema de la mochila Python: versión fraccionada
En la versión fraccionada del agoritmo de la mochila Python, puede agregar fracciones de objeto a la mochila.
clase BagObject:
def __init __ (self, weight, value, index):
self.index = índice
self.weight = peso
self.value = valor
self.report = valor // peso
#Función para la comparación entre dos BagObjects
# Comparamos el ratio calculado para ordenarlos
def __lt __ (yo, otro):
volver self.report & lt; otro.informe
def getMaxValue (peso, valores, capacidad):
arraySort = []
para i en rango (len (peso)):
arraySort.append (BagObject (peso [i], valores [i], i))
#Ordena los elementos de la bolsa por su informe
arraySort.sort (reverse = True)
counterValue = 0
para el objeto en arraySort:
currentWeight = int (object.weight)
currentValue = int (object.value)
si capacidad - peso actual> = 0:
# agregamos el objeto en la bolsa
# Restamos la capacidad
capacidad - = peso actual
counterValue + = currentValue
# Agregamos el valor en la bolsa
demás:
fracción = capacidad / peso actual
counterValue + = currentValue * fracción
capacitancia = int (capacitancia - (weightCurrent * fracción))
pausa
return counterValue
peso = [1,5,3,2,4]
valores = [10,50,20,30,60]
capacidad = 11
maxValue = getMaxValue (peso, valores, capacidad)
print ("Valor máximo en la mochila =", maxValue)
El resultado es el siguiente:
py sacados.py Valor máximo en la mochila = 140.0
Algoritmo de Python de enlaces internos:
https://128mots.com/index.php/category/python/ https://128mots.com/index.php/2021/01/21/algorithme-glouton-python/ https://128mots.com/index.php/2021/01/21/algorithme-glouton-python/ https://128mots.com/index.php/2021/01/19/levenshtein-python/ https://128mots.com/index.php/2021/01/19/levenshtein-python/ https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/ https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/
Algoritmo de Python de enlaces externos:
http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie .pdf
http://www.dil.univ-mrs.fr/ ~ gcolas / algo-license / slides / gloutons.pdf
