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

0/5 (10 avis)

Snippet vu 4 802 fois - Téléchargée 20 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
deadhand Messages postés 152 Date d'inscription dimanche 15 octobre 2006 Statut Membre Dernière intervention 27 août 2010 3
2 févr. 2010 à 15:46
Merci, mais je crois que c'est plus accessible que celà.
deadhand Messages postés 152 Date d'inscription dimanche 15 octobre 2006 Statut Membre Dernière intervention 27 août 2010 3
2 févr. 2010 à 13:04
LOL ! Au moins ca marche ! :)
ccgousset Messages postés 148 Date d'inscription samedi 1 août 2009 Statut Membre Dernière intervention 18 août 2021
2 févr. 2010 à 13:03
C'est mon avis tu as de la chance de pouvoir raisonner sur un probleme abstrait en le materialisant en C, cela n'est pas donné à tout le monde. Corrigé excuses.
ccgousset Messages postés 148 Date d'inscription samedi 1 août 2009 Statut Membre Dernière intervention 18 août 2021
2 févr. 2010 à 13:01
En C tu programme , du lot tu t'es extrait. Le reste viendra. C'est mon avis tu as de la chance pouvoir raisonner sur un prob abstarat en le materialisant en C n'est pas doné a nimporte qui. A plus
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 60
2 févr. 2010 à 12:45
Les conventions de nommages sont pas respectées, rien n'est modularisé, où sont les access modifier? méthodes abberantes telle que 'somme' qui peut s'écrire en une ligne, etc etc....
Afficher les 10 commentaires

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.