Recherche de deux sous ensemble dont les sommes des élèments sont egales
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 !
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.
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
- Recherche de deux sous ensemble dont les sommes des élèments sont egales
- Barre de recherche php - Forum PHP
- Eléments de blocage ✓ - Forum Visual Basic 6
- Recherche dans base mysql ✓ - Forum PHP
- Barre de recherche - Forum PHP
- Moteur de recherche PHP - MySQL ✓ - Forum PHP
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.