Newer
Older
minbp-algo est un programme développer dans le cadre du projet Bin-Packing
pour le module X1II030 Complexité et algorithmes à l'université de Nantes
il a pour objectif de tester le problème Min Bin-Packing définit comme suit :
-------------------------- MINIMUMBIN-PACKING(MIN-BP) --------------------------
-- Instance : Un ensemble d’objets O = {o_1, o_2 ... o_n} où chaque objet o_i --
-- possède une taille 0 < t_i ≤ 1, un ensemble de sacs S = {S_1, S_2... S_n}. --
-- Solution : Une répartition des objets de O dans les sacs de S telle que --
-- pour tout 1 ≤ j ≤ n, la somme des tailles des objets de S_j est inférieure --
-- ou ́egale à 1. --
-- Mesure : m, le nombre de sacs non vides. --
--------------------------------------------------------------------------------
Les instance de ce problème doivent être entrée sous la forme suivante :
n:t_1:t_2:t_3 ... t_n
Avec n le nombre d'objets et de sacs, t_1, t_2, t_3 ... t_n le poids des objets.
--------------------------------------------------------------------------------
--------------------------------- COMPIALATION ---------------------------------
--------------------------------------------------------------------------------
Dans le répertoir du projet (celui où se trouve ce même fichier README)
Éxecutez les commande suivant :
mkdir build && cd build
cmake ..
make
Puis lancer le programme directement avec
./minbp-algo
--------------------------------------------------------------------------------
----------------------------------- INSTANCES ----------------------------------
--------------------------------------------------------------------------------
Il y a des instances dans le dossier instances/