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