Algoritmo el problema de la mochila (problema de mochila) en más de 128 palabras

El problema de la mochila algorítmica es interesante y forma parte del primer programa de ciencia digital e informática.

Este problema ilustra los algoritmos glotón que enumeran todas las posibilidades de resolver un problema para encontrar la mejor solución.

El problema de la mochila es un problema de optimización, es decir, una función que debe ser maximizada o minimizada y restricciones que deben cumplirse.

El problema de la mochila

Para una mochila de máxima capacidad de artículos P y N cada uno con su propio peso y un valor establecido, tire los artículos dentro de la mochila para que el contenido final tenga el máximo valor.

Ejemplo de una declaración:

  • Capacidad máxima de la mochila: 11 unidades
  • Número de artículo: 5
  • Valores de objeto: $10.50,20,30.60
  • Peso de los objetos: ‘1,5,3,2,4’

¿Cuál es el valor máximo que se puede poner en la mochila teniendo en cuenta la restricción de capacidad máxima de la bolsa que es 11?

Algoritmo gluttonoso

Una solución eficaz es utilizar un algoritmo glotón. La idea es calcular la relación valor/peso para cada objeto y ordenar el objeto en función de esta relación calculada.

Toma el objeto con la proporción más alta y agrega hasta que no puedaagregar más.

En versión fraccionaria es posible añadir fracciones de artículo a la mochila.

Implementación del problema en versión no fraccionada

Aquí está una implementación del problema en una versión no fraccionada, es decir, no se puede agregar una fracción de un objeto a la bolsa. Solo se pueden agregar objetos enteros.

itemsac clase: 
    def __init__ (auto, peso, valor, índice): 
        self.index - índice         
        self.weight - peso 
        self.value
        self.report - valor // peso 
  #Fonction para la comparación entre dos ObjectsSac
  #On compara la relación calculada para ordenarlas
    def __lt__ (yo, otros): 
        devolver self.report< other.rapport 
  

def getValeurMax (pesos, valores, capacidad): 
        TableTrie[] 
        para i en el rango: 
            tableTrie.append (ObjectSac (peso[i]s, valore[i]s, i)) 
  
        #Trier los elementos de la bolsa por su informe
        tableTrie.sort (reverse - True) 
  
        MeterValeur - 0
        para el objeto en tableauTrie: 
            WeightCourant - int (object.weight) 
            ValueCourante - int (object.value) 
            si la capacidad - weightsCourant '0: 
                #on añade el objeto a la bolsa
                #On resta capacidad
                capacidad - weightsCourant 
                MeterValeur - ValueCourante
                #On añade valor a la bolsa 
        devolver contraValeur 


Pesos[1,5,3,2,4] 
Valores[10,50,20,30,60] 
capacidad - 11
Valor máximo - getValeurMax (peso, valores, capacidad) 
(valor máximo en la mochila", ValueMax) 

El resultado es el siguiente:

py sacados.py 
Valor máximo en mochila - 120

Implementación del problema en versión fraccionaria

En una versión fraccionaria del problema de la mochila se pueden añadir fracciones de objeto a la mochila.

itemsac clase: 
    def __init__ (auto, peso, valor, índice): 
        self.index - índice         
        self.weight - peso 
        self.value
        self.report - valor // peso 
  #Fonction para la comparación entre dos ObjectsSac
  #On compara la relación calculada para ordenarlas
    def __lt__ (yo, otros): 
        devolver self.report< other.rapport 
  

def getValeurMax (pesos, valores, capacidad): 
        TableTrie[] 
        para i en el rango: 
            tableTrie.append (ObjectSac (peso[i]s, valore[i]s, i)) 
  
        #Trier los elementos de la bolsa por su informe
        tableTrie.sort (reverse - True) 
  
        MeterValeur - 0
        para el objeto en tableauTrie: 
            WeightCourant - int (object.weight) 
            ValueCourante - int (object.value) 
            si la capacidad - weightsCourant '0: 
                #on añade el objeto a la bolsa
                #On resta capacidad
                capacidad - weightsCourant 
                MeterValeur - ValueCourante
                #On añade valor a la bolsa 
            Otro: 
                fracción - capacidad / pesoCouring 
                MeterValeur -Valor Courante - fracción 
                capacidad - int (capacidad - (weightsCourant - fracción)) 
                Romper
        devolver contraValeur 


Pesos[1,5,3,2,4] 
Valores[10,50,20,30,60] 
capacidad - 11
Valor máximo - getValeurMax (peso, valores, capacidad) 
(valor máximo en la mochila", ValueMax) 

El resultado es el siguiente:

py sacados.py 
Valor máximo en mochila - 140.0

Construir una aplicación paso a paso y descentralizada (Ethereum Blockchain Dapp) en más de 128 palabras – Parte 3

Este artículo sigue los dos primeros artículos sobre el tema:

Los primeros 2 artículos proporcionan una mejor comprensión del concepto de blockchain y aplicación descentralizada.

Creación del proyecto

Se crea un directorio para el proyecto de aplicación de votación en canciones.

mkdir vote-song-dapp

Para acelerar el desarrollo utilizaremos una "caja de trufa": https://www.trufflesuite.com/boxes

Es una especie de plantilla, un lienzo de aplicación que le permite centrarse en el Dapp al tener una estructura ya creada.

Basaré mi explicación en la caja de la tienda de mascotas disponible aquí: https://www.trufflesuite.com/tutorials/pet-shop. Este es uno de los primeros tutoriales de trufa para crear un Dapp.

Este cuadro de trufa incluye la estructura básica del proyecto, así como el código de la interfaz de usuario.

Utilice el comando trufero unbox:

trufa unbox pet-shop

Como recordatorio la instalación de la trufa es posible a través del pedido:

npm instalar -g trufa

Si abre la carpeta vote-chason-dapp con vscode, obtendrá el siguiente árbol:

Ejemplo de árbol de proyecto de aplicación Dapp (basado en trufa de tienda de mascotas)
  • contrato: almacenamiento del contrato inteligente de la aplicación
  • Migración: Las migraciones permiten transferir contratos inteligentes a la cadena de bloques Ethereum (prueba local o mainnet). Las migraciones también le permiten vincular contratos inteligentes con otros contratos inteligentes e iniciarlos.
  • node_modules: La carpeta node_modules contiene bibliotecas descargadas de npm.
  • src: Directorio de aplicaciones front-end (cliente)
  • prueba: Almacenamiento de pruebas para la aplicación
  • trufa-config.js: archivo Javascript que puede ejecutar cualquier código necesario para crear la configuración.

Creación del contrato inteligente

Como recordatorio estamos desarrollando una aplicación que permite elegir la canción favorita de los votantes.

Primero crearemos la parte que permite crear un voto para la mejor canción basada en 3 canciones elegibles.

El contrato escrito en solidez es el siguiente:

Contrato de TopChanson
        struct Song
        ID de uint;
        cadena de título;
        contador de uint;
    }
    uint contador públicoDeChansons;
    mapeo (uint - Canción) canciones públicas;

    función addChansonElligible (nomChanson de memoria de cadena) privada
        CounterDeChansons;
        cancion[compteurDeChansons]es - Song (CounterDeChansons, NameChanson, 0);
    }

    Función TopChansons(público)
        addChansonElligible ("Moonlight");
        addChansonElligible ("Mamá los botes pequeños");
        addChansonElligible (Ah! Cocodrilos");
    }

}

Tenga en cuenta el uso de "mapping (uint – Song) canciones públicas;"

Relacionado: https://solidity.readthedocs.io/en/v0.6.6/types.html#mapping-types

Esta estructura de datos nos permitirá almacenar los títulos de las canciones elegibles como una tabla hash. Es decir, una tabla que toma como clave de acceso en nuestro caso un uint que es el ID de la canción y permite recuperar el valor que es un tipo de canción estructurada.

El tipo de canción está estructurado, consulte la documentación de solidez: https://solidity.readthedocs.io/en/v0.6.6/types.html#structs

Aquí hay un caso especial en la característica addChansonElligible, toma en discusión el nombre de la canción que es una cadena de caracteres de cadena. Si no agrega la palabra clave "memory", obtendrá el siguiente error:

TypeError: la ubicación de los datos debe ser "almacenamiento" o "memoria" para el parámetro en función, pero no se ha dado ninguna.

Para la configuración de la función y las variables de retorno, la ubicación de los datos debe explicarse para todas las variables de tipo (struct, mapping, thong).

El contrato se migra a través del pedido:

trufa migrar --reset

Luego obtenemos:

Recopilando tus contratos...
===========================
Compilación de ./contracts/Migrations.sol
Compilación de ./contracts/TopChanson.sol

seguir…

Construir una aplicación paso a paso y descentralizada (Ethereum Blockchain Dapp) en más de 128 palabras – Parte 2

Este artículo sigue el primer artículo sobre el tema: http://128mots.com/index.php/2020/03/30/construire-une-application-decentralisee-full-stack-pas-a-pas-ethereum-blockchain-dapp-en-plus-de-128-mots-partie-1/

Ejemplo de aplicación de votación descentralizada (Dapp)

El usuario de la aplicación descentralizada necesita un monedero que contenga éter. Como se indica en el primer artículo es posible crear fácilmente una cartera en https://metamask.io/.

Primero usaremos la red ropsten. Ropsten Ethereum, también conocido como el "Ethereum Testnet", es, como su nombre indica, una red de prueba que realiza el mismo protocolo que Ethereum y se utiliza para fines de prueba antes de implementar en la red principal (Mainnet). https://ropsten.etherscan.io/

El uso nos permitirá crear y utilizar nuestra aplicación de forma gratuita antes de eventualmente transmitirla en la red principal de Ethereum.

Cuando el usuario se conecta a nuestra aplicación y a la red envía su voto y tiene que pagar algunas tarifas a través de su cartera con el fin de escribir su transacción en el Blockchain (llamado "Gas", este término se refiere a las tarifas para completar una transacción o ejecutar un contrato en la cadena de bloques Ethereum).

Arquitectura de aplicaciones Dapp

La arquitectura de la aplicación consta de un front-end que estará en HTML y Javascript. Este Frontend interactuará directamente con la cadena de bloques ethereum local que instalaremos.

Arquitectura de aplicaciones DAPP

Como se indica en el primer artículo, las reglas de negocio y la lógica se codificarán en un contrato inteligente. El Contrato Inteligente está escrito con el lenguaje de programación de solidez: https://solidity.readthedocs.io

Creación del Front-End

El front-end será simple que le permite mostrar el resultado de la votación para su canción favorita en forma de una lista y elegir de una lista desplegable la canción por la que desea votar.

Comprobar la instalación del nodo

nodo -v

Si el nodo no está instalado, puede consultar mi artículo sobre angular: http://128mots.com/index.php/2020/02/27/angular-en-plus-de-128-mots-partie-1/

Instalación de Metamask: Instalación de https://metamask.io/ como una extensión de su navegador

Instalación del marco de la trufa: La trufa es un entorno de desarrollo, un marco de pruebas y una canalización de activos para Ethereum, con el objetivo de hacer su vida más fácil como desarrollador de Ethereum. Proporciona herramientas que nos permiten escribir contactos inteligentes con el lenguaje de programación Solidity.

También se utilizará para desarrollar el front-end de la aplicación.

npm instalar -g trufa

Instalación de Ganache:

Ganache es una cadena de bloques personal para el desarrollo de Ethereum que puede utilizar para implementar contratos, desarrollar sus aplicaciones y ejecutar pruebas.

https://www.trufflesuite.com/ganache

Esto le permitirá tener una cadena de bloques local con 10 cuentas que están alimentadas con éter falso.

Comencé la aplicación y hice clic en Inicio rápido

Vemos las diferentes cuentas de nuestra cadena de bloques local.