## 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

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:

• 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.
• 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
}

}```

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

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```

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

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.

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/

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.