Recherche de deux sous ensemble dont les sommes des élèments sont egales

Soyez le premier à donner votre avis sur cette source.

Snippet vu 4 194 fois - Téléchargée 18 fois

Contenu du snippet

Il s'agit d'un algorithme générant un ensemble aléatoire de nombre sur une certaine plage et les répartissant sur deux sous-ensembles dont leurs sommes seraient égales. Il s'agit d'un sous problème du cas du sac à dos. C'est un problème NP complet.

Ceux qui sont à l'ESEO en I3 reconnaitront ce problème et pourront owned le prof !

Source / Exemple :


// Ecris par Loïc Angibaud , école ESEO , 2010
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Complexitude
{
    class Program
    {

        static bool verif(List<int> list1, List<int> list2) //Verifie que la somme des deux listes est egales
        {
           long res1 = 0;
           long res2 = 0;
            foreach (int i in list1)
            {
                res1 += i;
            }
            foreach (int i in list2)
            {
                res2 += i;
            }
            return res1 == res2;
        }

        static long somme(List<int> list) // Calcule la somme d'une liste
        {
            long res = 0;
            foreach (int i in list)
            {
                res += i;
            }
            return res;
        }

        static void affiche(List<int> list) // Affiche une liste
        {
            Console.Write('{');
            bool first = true;
            foreach (int i in list)
            {
                if (!first)
                    Console.Write(',');
                Console.Write(i);
                first = false;
            }
            Console.Write('}');
        }

        static List<int> initList(long initNB) //initialise le premier ensemble aleatoirement a partir d'un nombre
        {
            List<int> res = new List<int>();
            Random rndInit = new Random((int) initNB);
            Random rnd = new Random(rndInit.Next());
            for (int i = 0; i < 1024; i++ ) //Genere 1024 nombres
            {
                res.Add(rnd.Next(150000)); //Les nombres generes vont de 0 a 149999
            }
            return res;
        }

        static void Main(string[] args)
        {
            List<int> moyenne = new List<int>(); //Pour calculer la moyenne
            List<int> list=new List<int>();
            long sommeTotale=0;
            List<int> list1 = new List<int>();
            List<int> list2 = new List<int>();
            Console.WriteLine("Go !");
            int fin = 0;
            int max = 0;
            int min = 999999999;
            do
            {
                int somme1Rnd = 0;
                int somme2Rnd = 0;
                int nbEssai = 0;
                do
                {
                    list = initList(sommeTotale);
                    sommeTotale = somme(list);
                } while (sommeTotale % 2 != 0); //Supprime tout les cas de liste dont la somme total est impaire car ils ne sont pas resolvables

                List<int> temp = list;
                list1 = new List<int>();
                list2 = new List<int>();
                do
                {
                    list1.Add(temp.ElementAt(0));
                    temp.RemoveAt(0);
                    if (temp.Count > 0)
                    {
                        list2.Add(temp.ElementAt(0));
                        temp.RemoveAt(0);
                    }
                } while (temp.Count > 0); //Separe la liste en deux sous-ensemble. Un element sur deux va dans la liste de gauche et une element sur deux dans celle de droite

                if (!verif(list1, list2))
                {
                    do
                    {
                        nbEssai++;
                        long somme1 = somme(list1);
                        long somme2 = somme(list2);
                        if (somme1 > somme2)
                        {
                            int index = 0;
                            bool find = false;
                            for (index = 0; index < list1.Count; index++)
                            {
                                if (list1.ElementAt(index) < somme1 - somme2) //On prend le premier element qui est inferieur a la difference des deux sommes et on le met a la queue de l'autre liste
                                {
                                    find = true;
                                    break;
                                }
                            }
                            if (find)
                            {
                                list2.Insert(list2.Count-1,list1.ElementAt(index));
                                list1.RemoveAt(index);
                            }
                            else //On bouge un element au hasard de la liste dont la somme est la plus grande dans l'autre
                            {
                                Random rndInit = new Random();
                                Random rnd = new Random(rndInit.Next());
                                int i = rnd.Next(list1.Count);
                                list2.Add(list1.ElementAt(i));
                                list1.RemoveAt(i);
                                somme1Rnd++;
                            }
                        }
                        else
                        {
                            int index = 0;
                            bool find = false;
                            for (index = 0; index < list2.Count; index++)
                            {
                                if (list2.ElementAt(index) < somme2 - somme1)//On prend le premier element qui est inferieur a la difference des deux sommes et on le met a la queue de l'autre liste
                                {
                                    find = true;
                                    break;
                                }
                            }
                            if (find)
                            {
                                list1.Insert(list1.Count - 1, list2.ElementAt(index));
                                list2.RemoveAt(index);
                            }
                            else //On bouge un element au hasard de la liste dont la somme est la plus grande dans l'autre
                            {
                                Random rndInit = new Random();
                                Random rnd = new Random(rndInit.Next());
                                int i = rnd.Next(list2.Count);
                                list1.Add(list2.ElementAt(i));
                                list2.RemoveAt(i);
                                somme2Rnd++;
                            }
                        }
                    } while (!verif(list1, list2)); //Tant qu'on a pas de solutions
                }
                Console.WriteLine("\nEND\nCycle : "+fin+"\nSolution atteinte en "+(nbEssai-1)+" essais : "+somme1Rnd+" , "+somme2Rnd); // Affiche le nombre d'étapes pour trouver la solution et le nombre de fois qu'un nombre a été déplacé aléatoirement dans les deux cas ci-dessus (premier cas : somme 1 > somme2, deuxieme cas : Somme 2 > somme 1)
                fin++;
                moyenne.Add(nbEssai);
                if (nbEssai > max)
                    max = nbEssai;
                if (nbEssai < min)
                    min = nbEssai;
            } while (fin != 300000); //Refait le test 300000 fois puis affiche la moyenne
            Console.WriteLine("\n\nSur "+fin+" cycles -> Moyenne = " + somme(moyenne) / moyenne.Count+"\nMax -> "+max+" Min -> "+min);
            Console.ReadLine(); //taper une touche pour finir
        }
    }
}

Conclusion :


Ce programme trouve, dans la majorité des cas, une solution mais il s'agit d'un problème NP complet (qui n'admet pas de solutions dans tout les cas). Tout les cas de somme impaire sont rejetés et il n'y a pas de cas d'arrêts si aucune solution n'est trouvée.

Il est a noter que la rapidité de convergence est dûe au fait de l'utilisation de List<> pour enregistrer les resultats, lorsqu'un element est deplace, il s'agit juste quasiment d'un MOV au niveau assembleur. Cela nécessite donc très peu de temps de cycle pour realiser une operation basique.

A voir également

Ajouter un commentaire

Commentaires

ccgousset
Messages postés
145
Date d'inscription
samedi 1 août 2009
Statut
Membre
Dernière intervention
23 juillet 2019
-
A ce beau les maths. J'ai 20 ou plus segments dont les mesures varient de -x a +x dixiemes de millimetres. Je veux en faire deux ensembles (de 10 segments chacuns) de longueurs les plus proches possibles. Ormis une methode de crible comme tu utilise connais tu un algoritme pour traiter ce cas ? (ce a dire a priori sans essayer toutes les solutions possibles) . Si tu as une formule fais m'en part.Merci
deadhand
Messages postés
159
Date d'inscription
dimanche 15 octobre 2006
Statut
Membre
Dernière intervention
27 août 2010
4 -
Désolé mais j'ai fait cet algo pour un repondre a un probleme posé en TP pour un cours de complexitude de *š$^% alors je t'avoue que pour les algo de même type que le tien, rien ne vaux une méthode bourrin et à la main !
ccgousset
Messages postés
145
Date d'inscription
samedi 1 août 2009
Statut
Membre
Dernière intervention
23 juillet 2019
-
Merci quand meme monsieur l'ingenieur. A plus
cs_Bidou
Messages postés
5507
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
41 -
Niveau coding, on est proche de la catastrophe....
deadhand
Messages postés
159
Date d'inscription
dimanche 15 octobre 2006
Statut
Membre
Dernière intervention
27 août 2010
4 -
Lol ! Et pourquoi ?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.