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

Leave a Reply

Your email address will not be published. Required fields are marked *