O problema da mochila algorítmica (e sua implementação em python) é interessante e faz parte do primeiro programa digital e de ciência da computação.
Este problema ilustra algoritmos gananciosos que enumeram todas as possibilidades de resolver um problema para encontrar a melhor solução.
O problema da mochila de algoritmos python é um problema de otimização, ou seja, uma função que deve ser maximizada ou minimizada e restrições que devem ser satisfeitas.
O problema da mochila – algoritmo Python
Para uma mochila de capacidade máxima de P e N itens, cada um com seu próprio peso e um valor definido, descarte os itens de dentro da mochila para que o conteúdo final tenha o valor máximo.
Exemplo de declaração:
- Capacidade máxima da mochila: 11 unidades
- Número de itens: 5
- Valores dos itens: {10,50,20,30,60}
Qual é o valor máximo que pode ser colocado na mochila considerando a restrição de capacidade máxima da bolsa que é 11?
Algoritmo ganancioso python
Uma solução eficiente é usar um algoritmo guloso. A ideia é calcular a relação valor / peso de cada objeto e classificar o objeto com base nessa relação calculada.
Pegamos o objeto com a proporção mais alta e adicionamos até que não possamos adicionar mais.
Na versão fracionária é possível adicionar frações do artigo à mochila.
Implementação do problema de mochila Python – versão não fracionária
Aqui está uma implementação do problema da mochila python em versão não fracionária, ou seja, não se pode adicionar uma fração de um objeto na bolsa. Apenas objetos inteiros podem ser adicionados.
classe BagObject:
def __init __ (próprio, peso, valor, índice):
self.index = index
self.weight = weight
self.value = value
self.report = value // weight
#Função para comparação entre dois BagObjects
# Comparamos a proporção calculada para classificá-los
def __lt __ (self, other):
return self.report & lt; other.report
def getMaxValue (peso, valores, capacidade):
arraySort = []
para i no intervalo (len (peso)):
arraySort.append (BagObject (weight [i], values [i], i))
# Classifique os elementos da sacola por seu relatório
arraySort.sort (reverse = True)
counterValue = 0
para objeto em arraySort:
currentWeight = int (object.weight)
currentValue = int (object.value)
se capacidade - peso atual> = 0:
# adicionamos o objeto no saco
# Nós subtraímos a capacidade
capacidade - = peso atual
counterValue + = currentValue
# Nós adicionamos o valor no saco
return counterValue
peso = [1,5,3,2,4]
valores = [10,50,20,30,60]
capacidade = 11
maxValue = getMaxValue (peso, valores, capacidade)
print ("Max value in the backpack =", maxValue)
O resultado é o seguinte:
py sacados.py Valor máximo na mochila = 120
Implementação do problema de mochila Python – versão fracionária
Na versão fracionária do agoritmo da mochila python, você pode adicionar frações do objeto à mochila.
classe BagObject:
def __init __ (próprio, peso, valor, índice):
self.index = index
self.weight = weight
self.value = value
self.report = value // weight
#Função para comparação entre dois BagObjects
# Comparamos a proporção calculada para classificá-los
def __lt __ (self, other):
return self.report & lt; other.report
def getMaxValue (peso, valores, capacidade):
arraySort = []
para i no intervalo (len (peso)):
arraySort.append (BagObject (weight [i], values [i], i))
# Classifique os elementos da sacola por seu relatório
arraySort.sort (reverse = True)
counterValue = 0
para objeto em arraySort:
currentWeight = int (object.weight)
currentValue = int (object.value)
se capacidade - peso atual> = 0:
# adicionamos o objeto no saco
# Nós subtraímos a capacidade
capacidade - = peso atual
counterValue + = currentValue
# Nós adicionamos o valor no saco
outro:
fração = capacidade / peso atual
counterValue + = currentValue * fração
capacitância = int (capacitância - (peso atual * fração))
intervalo
return counterValue
peso = [1,5,3,2,4]
valores = [10,50,20,30,60]
capacidade = 11
maxValue = getMaxValue (peso, valores, capacidade)
print ("Max value in the backpack =", maxValue)
O resultado é o seguinte:
py sacados.py Valor máximo na mochila = 140,0
Algoritmo Python de links 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 Python de links externos:
http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie .pdf
http://www.dil.univ-mrs.fr/ ~ gcolas / algo-license / slides / gloutons.pdf