Algorithm the problem of the backpack (Knapsack problem) in more than 128 words

The problem of the algorithmic backpack is interesting and is part of the first digital science and computer science program.

This problem illustrates the gluttonous algorithms that list all the possibilities of solving a problem to find the best solution.

The problem of the backpack is a problem of optimization, i.e. a function that must be maximized or minimized and constraints that must be met.

The problem of the backpack

For a backpack of maximum capacity of P and N items each with its own weight and a set value, throw the items inside the backpack so that the final contents have maximum value.

Example of a statement:

  • Maximum backpack capacity: 11 units
  • Item number: 5
  • Object Values: $10.50,20,30.60
  • Weight of Objects: '1,5,3,2,4'

What is the maximum value that can be put in the backpack considering the maximum capacity constraint of the bag which is 11?

Gluttonous algorithm

An effective solution is to use a gluttonous algorithm. The idea is to calculate the value/weight ratio for each object and sort the object based on this calculated ratio.

You take the object with the highest ratio and add until you can't add any more.

In fractional version it is possible to add fractions of item to the backpack.

Implementation of the problem in non-fractional version

Here is an implementation of the problem in a non-fractional version, i.e. you can't add a fraction of an object to the bag. Only whole objects can be added.

itemsac class: 
    def __init__ (self, weight, value, index): 
        self.index - index         
        self.weight - weight 
        self.value
        self.report - value // weight 
  #Fonction for comparison between two ObjectsSac
  #On compares the ratio calculated to sort them
    def __lt__ (self, other): 
        return self.report< other.rapport 
  

def getValeurMax (weights, values, ability): 
        TableTrie[] 
        for i in range: 
            tableTrie.append (ObjectSac (weigh[i]ts, value[i]s, i)) 
  
        #Trier the elements of the bag by their report
        tableTrie.sort (reverse - True) 
  
        MeterValeur - 0
        for object in tableauTrie: 
            WeightCourant - int (object.weight) 
            ValueCourante - int (object.value) 
            if capacity - weightsCourant '0: 
                #on adds the object to the bag
                #On subtracts capacity
                capacity - weightsCourant 
                MeterValeur - ValueCourante
                #On adds value to the bag 
        return counterValeur 


Weights[1,5,3,2,4] 
Values[10,50,20,30,60] 
capacity - 11
Maximum value - getValeurMax (weight, values, capacity) 
print ("Maximum value in the backpack," ValueMax) 

The result is as follows:

py sacados.py 
Maximum value in backpack - 120

Implementation of the problem in fractional version

In a fractional version of the backpack problem you can add fractions of object to the backpack.

itemsac class: 
    def __init__ (self, weight, value, index): 
        self.index - index         
        self.weight - weight 
        self.value
        self.report - value // weight 
  #Fonction for comparison between two ObjectsSac
  #On compares the ratio calculated to sort them
    def __lt__ (self, other): 
        return self.report< other.rapport 
  

def getValeurMax (weights, values, ability): 
        TableTrie[] 
        for i in range: 
            tableTrie.append (ObjectSac (weigh[i]ts, value[i]s, i)) 
  
        #Trier the elements of the bag by their report
        tableTrie.sort (reverse - True) 
  
        MeterValeur - 0
        for object in tableauTrie: 
            WeightCourant - int (object.weight) 
            ValueCourante - int (object.value) 
            if capacity - weightsCourant '0: 
                #on adds the object to the bag
                #On subtracts capacity
                capacity - weightsCourant 
                MeterValeur - ValueCourante
                #On adds value to the bag 
            else 
                fraction - capacity / weightCouring 
                MeterValeur -Courante value - fraction 
                capacity - int (capacity - (weightsCourant - fraction)) 
                Break
        return counterValeur 


Weights[1,5,3,2,4] 
Values[10,50,20,30,60] 
capacity - 11
Maximum value - getValeurMax (weight, values, capacity) 
print ("Maximum value in the backpack," ValueMax) 

The result is as follows:

py sacados.py 
Maximum value in backpack - 140.0

Build a step-by-step, decentralized application (Ethereum Blockchain Dapp) in more than 128 words – Part 3

This article follows the first two articles on the subject:

The first 2 articles provide a better understanding of the concept of blockchain and decentralized application.

Creating the project

A directory is created for the voting application project on songs.

mkdir vote-song-dapp

To accelerate development we will use a "truffle box": https://www.trufflesuite.com/boxes

It's sort of a template, an application canvas that allows you to focus on the Dapp by having a structure already created.

I will base my explanation on the pet-shop box available here: https://www.trufflesuite.com/tutorials/pet-shop. This is one of the first truffle tutorials to create a Dapp.

This truffle box includes the basic structure of the project as well as the user interface code.

Use the truffle unbox command:

truffle unbox pet-shop

As a reminder the installation of truffle is possible via the order:

npm install -g truffle

If you open the vote-chason-dapp folder with vscode then you get the following tree:

Dapp app project tree example (based on truffle pet-shop)
  • contract: storage of the application's smart contract
  • migration: Migrations allow smart contracts to be transferred to the Ethereum blockchain (local test or mainnet). Migrations also allow you to link smart contracts with other smart contracts and start them.
  • node_modules: The node_modules folder contains libraries downloaded from npm.
  • src: Front-end application directory (customer)
  • test: Storage of tests for the application
  • truffle-config.js: Javascript file that can execute any code needed to create your configuration.

Creating the smart contract

As a reminder we are developing an application that allows to elect the favorite song of voters.

We will first create the part that allows to create a vote for the best song based on 3 eligible songs.

The contract written in solidity is as follows:

TopChanson contract
        struct Song
        uint ID;
        title string;
        uint counter;
    }
    uint public counterDeChansons;
    mapping (uint - Song) public songs;

    function addChansonElligible (string memory nomChanson) private
        CounterDeChansons;
        songs -[compteurDeChansons] Song (CounterDeChansons, NameChanson, 0);
    }

    TopChansons(public) function
        addChansonElligible ("Moonlight");
        addChansonElligible ("Mom the little boats");
        addChansonElligible ("Ah! Crocodiles");
    }

}

Note the use of "mapping (uint – Song) public songs;"

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

This data structure will allow us to store the titles of eligible songs like a hash table. That is, a table that takes as an access key in our case a uint that is the song ID and allows to recover the value that is a structured song type.

The Song type is structured, see solidity documentation: https://solidity.readthedocs.io/en/v0.6.6/types.html#structs

Here there is a special case on the feature addChansonElligible, it takes into argument the name of the song which is a string character chain. If you don't add the keyword "memory" you get the following error:

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

For function settings and return variables, the location of the data must be explained for all type variables (struct, mapping, thong).

The contract is migrated via the order:

truffle migrate --reset

We then get:

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

To follow …

Build a step-by-step, decentralized application (Ethereum Blockchain Dapp) in more than 128 words – Part 2

This article follows the first article on the subject: 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/

Example of decentralized voting application (Dapp)

The user of the decentralized application needs a wallet that contains Ether. As stated in the first article it is possible to easily create a wallet on https://metamask.io/.

First we will use the ropsten network. Ropsten Ethereum, also known as the "Ethereum Testnet", is, as the name suggests, a test network that performs the same protocol as Ethereum and is used for testing purposes before deploying on the main network (Mainnet). https://ropsten.etherscan.io/

The use will allow us to create and use our app for free before eventually broadcasting it on Ethereum's main network.

When the user connects to our application and the network he sends his vote and has to pay a few fees via his wallet in order to write his transaction in the Blockchain (called "Gas", this term refers to the fees to complete a transaction or execute a contract on the Ethereum blockchain).

Dapp app architecture

The application architecture consists of a front-end that will be in HTML and Javascript. This Frontend will engage directly with the local ethereum blockchain that we will install.

DAPP app architecture

As stated in the first article the business rules and logic will be coded in a Smart Contract. The Smart Contract is written with the solidity programming language: https://solidity.readthedocs.io

Creation of the Front-End

The front-end will be simple it allows you to display the result of the vote for your favorite song in the form of a list and to choose from a drop-down list the song for which you wish to vote.

Check node installation

node -v

If node is not installed you can refer to my article on angular: http://128mots.com/index.php/2020/02/27/angular-en-plus-de-128-mots-partie-1/

Metamask installation: Installing https://metamask.io/ as an extension of your browser

Installation of the truffle framework: Truffle is a development environment, a testing framework and an asset pipeline for Ethereum, aimed at making your life easier as an Ethereum developer. It provides tools that allow us to write intelligent contacts with the Solidity programming language.

It will also be used to develop the front-end of the application.

npm install -g truffle

Ganache installation:

Ganache is a personal blockchain for Ethereum development that you can use to deploy contracts, develop your applications and run tests.

https://www.trufflesuite.com/ganache

This will allow you to have a local blockchain with 10 accounts that are powered with fake Ether.

I started the app and clicked Quick Start

We see the different accounts of our local blockchain.