Problème du sac à dos – Algorithme en Python (knapsack problem)

Le problème du sac à dos en algorithmique (et son implémentation python) est intéressant et fait parti du programme de Sciences numériques et informatique de première.

Ce problème illustre les algorithmes gloutons qui énumèrent toutes les possibilités de résolution d’un problème pour trouver la meilleure solution.

Le problème du sac à dos algorithme python est un problème d’optimisation, c’est à dire une fonction que l’on doit maximiser ou minimiser et des contraintes qu’il faut satisfaire.

Le problème du sac à dos – algorithme Python

Pour un sac à dos de capacité maximale de P et N articles chacun avec son propre poids et une valeur définie, jetez les articles à l’intérieur du sac à dos de telle sorte que le contenu final ait la valeur maximale.

Le problème du sac à dos - algorithme Python

Exemple d’énoncé :

  • Capacité maximum du sac à dos : 11 unités
  • Nombre d’objet : 5
  • Valeurs des objets : {10,50,20,30,60}
  • Poids des objets : {1,5,3,2,4}

Quelles est la valeur maximum qu’il est possible de mettre dans le sac à dos en considérant la contrainte de capacité maximum du sac qui est de 11 ?

Algorithme glouton python

Une solution efficace consiste à utiliser un algorithme glouton. L’idée est de calculer le rapport valeur / poids pour chaque objet et de trier l’objet sur la base de ce rapport calculé .

On prends l’objet avec le ratio le plus élevé et on ajoute jusqu’à ce qu’on ne puisse plus en ajouter.

En version fractionnaire il est possible d’ajouter des fractions d’article au sac à dos.

Implémentation du problème du sac à dos Python – version non fractionnaire

Voici une implémentation du problème du sac à dos python en version non fractionnaire, c’est à dire qu’on ne peut pas ajouter de fraction d’un objet dans le sac. Seul des objets entiers peuvent être ajoutés.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 120

Implémentation du problème du sac à dos python – version fractionnaire

En version fractionnaire de l’agorithme du sac à dos python on peut ajouter des fractions d’objet au sac à dos.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
            else: 
                fraction = capacite / poidsCourant 
                compteurValeur += valeurCourante * fraction 
                capacite = int(capacite - (poidsCourant * fraction)) 
                break
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 140.0

Liens internes algorithme python :

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/19/levenshtein-python/
https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

Liens externes algorithme python :

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 3

Cet article fait suite aux deux premiers articles sur le sujet :

Les 2 premiers articles permettent de mieux comprendre le concept de blockchain et d’application décentralisée.

Création du projet

On crée un répertoire pour le projet d’application de vote sur des chansons.

mkdir vote-chanson-dapp

Pour accélérer le développement on va utiliser une « truffle box » : https://www.trufflesuite.com/boxes

C’est en quelques sorte un modèle, un canevas d’application qui vous permet de vous focaliser sur la Dapp en ayant une structure déjà créée.

Je vais baser mon explication sur la pet-shop box disponible ici : https://www.trufflesuite.com/tutorials/pet-shop. C’est un des premiers tutos de truffle pour créer une Dapp.

Cette truffle box comprend la structure de base du projet ainsi que le code de l’interface utilisateur.

Utilisez la commande truffle unbox :

truffle unbox pet-shop

Pour rappel l’installation de truffle est possible via la commande :

npm install -g truffle

Si vous ouvrez le dossier vote-chason-dapp avec vscode vous obtenez alors l’arborescence suivante :

Arborescence du projet de l’application Dapp exemple (basée sur pet-shop de truffle)
  • contract : stockage du smart contract de l’application
  • migration : Les migrations permettent de transférer les smarts contracts vers la blockchain Ethereum (en local test ou mainnet). Les migrations permettent également de relier des smart contrats avec d’autres smarts contracts et de les initialiser.
  • node_modules : Le dossier node_modules contient les bibliothèques téléchargées depuis npm.
  • src : Répertoire de l’application front-end (client)
  • test : Stockage des tests pour l’application
  • truffle-config.js : fichier Javascript qui peut exécuter tout code nécessaire pour créer votre configuration.

Création du smart contract

Pour rappel nous développons une application qui permet d’élire la chanson préférée des électeurs.

Nous allons créer dans un premier temps la partie qui permet de créer un vote pour la meilleure chanson basée sur 3 chansons éligibles.

Le contrat écrit en solidity est le suivant :

contract TopChanson {
        struct Chanson {
        uint identifiant;
        string titre;
        uint compteur;
    }
    uint public compteurDeChansons;
    mapping(uint => Chanson) public chansons;

    function ajouterChansonElligible (string memory nomChanson) private {
        compteurDeChansons ++;
        chansons[compteurDeChansons] = Chanson(compteurDeChansons, nomChanson, 0);
    }

    function TopChansons() public {
        ajouterChansonElligible("Au clair de la lune");
        ajouterChansonElligible("Maman les p'tits bateaux");
        ajouterChansonElligible("Ah ! Les crocodiles");
    }

}

A noter l’utilisation de « mapping(uint => Chanson) public chansons; »

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

Cette structure de donnée va nous permettre de stocker les titres des chansons éligibles à la façon d’une table de hachage. C’est à dire un tableau qui prend pour clé d’accès dans notre cas un uint qui est l’identifiant de la chanson et permet de récupérer la valeur qui est un type Chanson structuré.

Le type Chanson est structuré, voir la documentation solidity : https://solidity.readthedocs.io/en/v0.6.6/types.html#structs

Ici il y a un cas particulier sur la fonction ajouterChansonElligible, elle prends en argument le nom de la chanson qui est une chaine de caractère STRING. Si on ajoute pas le mot clé « memory » on obtient l’erreur suivante:

TypeError: Data location must be « storage » or « memory » for parameter in function, but none was given.

Pour les paramètres de fonction et les variables de retour, l’emplacement des données doit être explicité pour toutes les variables de type (struct, mapping, string).

La migration du contrat s’effectue via la commande :

truffle migrate --reset

On obtient alors :

Compiling your contracts...
===========================
> Compiling ./contracts/Migrations.sol
> Compiling ./contracts/TopChanson.sol

A suivre …

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 2

Cet article fait suite au premier article sur le sujet : https://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/

Exemple d’application décentralisée (Dapp) de vote

L’utilisateur de l’application décentralisée a besoin d’un portefeuille qui contient des Ether. Comme indiqué dans le premier article il est possible de se créer facilement un wallet sur https://metamask.io/.

Dans un premier temps nous utiliserons le réseau ropsten. Ropsten Ethereum, également connu sous le nom de «Ethereum Testnet», est comme son nom l’indique, un réseau de test qui exécute le même protocole qu’Ethereum et est utilisé à des fins de test avant de se déployer sur le réseau principal (Mainnet). https://ropsten.etherscan.io/

L’utilisation va nous permettre de créer et d’utiliser gratuitement notre application avant d’éventuellement la diffuser sur le réseau principal d’Ethereum.

Lorsque l’utilisateur se connecte à notre application et au réseau il envoie son vote et doit payer quelques frais via son portefeuille afin d’écrire sa transaction dans la Blockchain (Appelé « Gas », ce terme se réfère aux frais pour mener à bien une transaction ou exécuter un contrat sur la blockchain Ethereum).

Architecture de l’application Dapp

L’architecture de l’application se compose d’un front-end qui sera en HTML et Javascript. Ce Frontend dialoguera directement avec la blockchain ethereum local que nous installerons.

Architecture de l’application DAPP

Comme indiqué dans le premier article les règles métier et la logique seront codées dans un Smart Contract. Le Smart Contract est rédigé avec le langage de programmation solidity : https://solidity.readthedocs.io

Création du Front-End

Le front-end sera simple il permet d’afficher le résultat du vote pour sa chanson préférée sous forme d’une liste et de choisir dans une liste déroulante la chanson pour laquelle on souhaite voter.

Vérifier l’installation de node

node -v

Si node n’est pas installé vous pouvez vous référer à mon article sur angular : https://128mots.com/index.php/2020/02/27/angular-en-plus-de-128-mots-partie-1/

Installation de Metamask : il s’agit d’installer https://metamask.io/ en tant qu’extension de votre navigateur

Installation du framework truffle : Truffle est un environnement de développement, un cadre de test et un pipeline d’actifs pour Ethereum, visant à vous faciliter la vie en tant que développeur Ethereum. Il fournit des outils qui nous permettent d’écrire des contacts intelligents avec le langage de programmation Solidity.

Il sera également utilisé pour développer le front-end de l’application.

npm install -g truffle

Installation de Ganache :

Ganache est une blockchain personnelle pour le développement Ethereum que vous pouvez utiliser pour déployer des contrats, développer vos applications et exécuter des tests.

https://www.trufflesuite.com/ganache

Cela va vous permettre d’avoir une blockchain locale avec 10 comptes qui sont alimenté avec des faux Ether.

J’ai démarré l’application et j’ai cliqué sur Quick Start

On voit s’afficher les différents comptes de notre blockchain locale.