bonjour,
 
mon problème me semble plutot simple mais je ne suis pas du tout spécialiste dans les algo et du coup j'ai un peu de mal pour trouver une piste (j'espere que ca pas été donné 2 pages avant   )
 
donc voila le truc :
j'ai en entrée un tableau d'entier qui peut dépasser 50 elements et une valeur A à trouver
j'aimerais connaitre la meilleurs combinaisons (celles necessitant le moins d'entiers) pour obtenir la valeur A.
 
je ne pense pas que la solution de tester toutes les combinaisons soit la bonne puisque le nombre de possibilités sera énorme , non ?
donc si quelqu'un a une idée du type d'algo à utiliser, je l'en remercierais beaucoup

C'est quoi les operations que tu as le droit de faire avec tes entiers?  
Est-ce qu'ils peuvent etre negatifs?

Yep, je suis là en amateur.
Je pensais à passer par une racine de A

les entiers ne peuvent pas être négatifs et la seule opération sur les entiers est la somme.
 
par exemple , si en entrée j'ai 3,4,3,2 et que le valeur a trouver est 9 je dois avoir en sortie 3,4,2

ça pue l'exo de cours.

Tes valeurs dans le tableau sont rangées ?

ca ressemble à du knapsack ca non ?

 
le pire est que j'ai peut etre du faire ca en cours ... mais ca fait plus de 10 ans que j'ai fini la fac
 
sinon non mes valeurs ne sont pas rangées mais ca ce n'est pas un pb , je peux les ranger avant si besoin
 
sinon Joel F,merci je vais regarder de ce pas le knapsack sur wikipedia...

Bah algorithmiquement tu peux émettre des hypothèses qui permettront de tendre vers un bon algorithme optimisé par le bon sens :
- puisque l'on veut le moins d'élément alors il vaut mieux prendre les élements les plus grands en priorité
-> tri en ordre décroissant
- après tu combines en suivant l'ordre décroissant
- peut-être avec une technique de décalage vers la fin pour prendre les plus petits éléments qui eux se casent mieux

Le bon sens   ? Pas si sur que ce soit interessant de commencer par les elements les plus grands. Si je dois trouver 10 et que j'ai comme nombres 9 8 7 6 5 4 3 2 1 ...
En fait ca depend si on cherche a s'approcher au max de 10, ou si on cherche uniquement les solutions exactes.

En cherchant les plus proche <= des quotients de A/i + le reste pour i 1..A.

 
Tirage avec ou sans remise ?
 
De quel rang est A ?
De quel rang sont les entiers opérants ?

 
A ce moment là si tu fais avec le bon sens, tu prends 9, puis 8 tu vois que ça fait dépasser 10, donc tu retires 8 et tu prends le plus petit élément qui est 1. Ca c'est avec ce cas (et en supposant que la fonction à appliquer entre éléments est une addition), avec une autre cas ca ne marchera pas forcément aussi bien, mais le but c'est de faire tendre l'algorithme vers quelque chose d'optimisé. Par exemple si on veut chercher A = 8, on aurait prit 9 on aurait vu que d'entrée ça dépasse, donc on serait passer à 8. S'il n'y avait pas 8 dans l'ensemble on aurait eu 7, puis on aurait pris 1 et rebelotte. Bah que du bon sens.
 
Après s'il est fort en maths, il peut sortir les innombrables théories du chapeau, et faire des démonstrations pour démontrer qu'il a trouvé la solution idéale, pour dénombrer le nombre de solutions idéales qui existent.

knapsack j'ai deja dit

Yep,
Je ne sais pas si ça peut le faire... Voici un code Ada, si vous aviez un fichier de teste...
 

with Text_Io; use Text_Io;
procedure Main is
 
   type T_Tab is array(Positive range <> ) of Integer;
   type Tab_Access is access all T_Tab;
 
   Impossible : Exception;
 
 
   function Total(Init : in T_Tab) return Natural is
      Somme : Natural := 0;
   begin
      for I in Init'range loop
         Somme := Somme + Init(I);
      end loop;
 
      return Somme;
   end Total;
 
 
   function Dico(Init : in T_Tab; x : in positive) return natural is
 
      début : Natural := 1;
      Fin : Natural := Init'Length;
      Milieu : Natural := Fin;
      verax : Boolean := false;
   begin
      while début <= fin loop
         Milieu := (début+Fin)/2;
         case Verax is
            when False =>
               while Milieu > 0 and then Init(Milieu) = 0 loop
                  Milieu := Milieu - 1;
               end loop;
            when True =>
               while Milieu < Init'Length and then Init(Milieu) = 0 loop
                  Milieu := Milieu + 1;
               end loop;
         end case;
         if Milieu < 1 or Milieu > Init'length then
 
            case Verax is
               when False =>
                  while Milieu > 0 and then Init(Milieu) = 0 loop
                     Milieu := Milieu - 1;
                  end loop;
               when True =>
                  while Milieu < Init'Length and then Init(Milieu) = 0 loop
                     Milieu := Milieu + 1;
                  end loop;
            end case;
            return Milieu;
         else
            if Init(Milieu) < X then
               Début := Milieu+1;
               Verax := True;
            else
               if Init(Milieu) = X then
 
                  return Milieu;
               else
                  Fin := Milieu - 1;
                  Verax := False;
               end if;
            end if;
         end if;
      end loop;
      return 0;
   end Dico;
   procedure Sigma(Init : in out T_Tab; Dividande : in Positive) is
      Save_Init : T_Tab := Init;
      Save_Reste : T_Tab := Init;
      Diviseur_Quotient, Diviseur_reste : Positive := 1;
      Multiple : Natural := 1;
      somme : Natural := 0;
      Reste    : Natural := 0;
      Index    : Natural := Init'length;
      Total_init    : Natural := 0;
   begin
      Total_init := Total(Init);
      --------------------------------------------
      -- Ckeck impossible et solution immediate --
      if Total_Init < Dividande then
         raise Impossible;
      elsif Total_Init = Dividande then
         for I in Init'Range loop
            Init(I) := 0;
         end loop;
         return;
      end if;
      loop
 
 
         loop
 
            Index := Dico(Init,(Dividande-Somme)/Diviseur_quotient);
            if Index = 0 then
               exit;
            end If;
            Somme := Somme + Init(Index);
 
            Init(Index) := 0;
            if Somme = Dividande then
               return;
            end if;
            exit when Multiple = Diviseur_quotient;
            Multiple := Multiple + 1;
         end loop;
         Reste := 0;
 
         Save_Reste := Init;
         Diviseur_reste := 1;
         loop
 
 
            if Dividande - somme = 0 then
               return;
            end if;
            Reste := Dividande - Somme;
            Index := Dico(Save_reste,Reste);
            if Index = 0 then
               exit;
            end If;
            Reste := Reste - Save_reste(Index);
            Save_reste(Index) := 0;
            if Reste = 0 then
                  Init := Save_Reste;
                  return;
            end if;
            Diviseur_reste := Diviseur_reste + 1;
            exit when Diviseur_reste > reste;
         end loop;
         Diviseur_quotient := Diviseur_quotient + 1;
 
         Somme := 0;
         Init := Save_Init;
         Multiple := 1;
         exit when Diviseur_Quotient > Dividande;
      end loop;
 
      raise Impossible;
 
   end Sigma;
 
   Test :  T_Tab := (1,2,3,4,5,6,7,8,9);
   Solution : T_Tab := Test;
   A : Positive := 1;
begin
   Sigma(solution, A);
   for I in 1..Solution'Length loop
      if Solution(I) = 0 then
         Put(Natural'Image(Test(I)));
      end if;
   end loop;
end Main;

Re yep,
Peut- être des truc en trop. Tout le monde sais lire.  
 
edit : je ne sais plus, je me relirai demain.
 
edit : Incomplet tout de suite, je viends de tester une config, et ça ne fonctionne pas.
 
        je mettrai le truc en ligne à l'adresse ci dessous : Code Sigma

bordel les mecs arretez d'inventer la roue quoi

D'ailleurs, knapsack (puisque c'est bien de ca qu'il s'agit), c'est pas NP-complet par hasard ?

justement.

 
Si mais y a de bonnes heuristiques pour le résoudre.
Alors voir jovalise & co jeter des algo en 10mn ca me fait bien rigoler
 

Meme quand le probleme est facile les algos de jovalise sont marrants.    

 
Deja , les algo en ADA ... je dirais rien; Ensuite, c'ets comme si je me permettait d'aller sur la cat PHP/MySQL pondre des requetes/scripts qui ont ni têtes ni têtes

je vous remercie tous de vos réponses, la solution du sac à dos semble tres bien remplir son rôle

Si je ne m'abuse, l'algo du sac à dos (d'après la première ligne de Wiki du moins) ne répond pas au problème.
C'est proche, mais pas bon.
 
En effet, avec le sac à dos, on tente de remplir le plus possible le sac à dos. On ne se soucie donc pas du nombre d'éléments.
Alors qu'ici, on veut non seulement remplir le sac, mais limiter au minimum le nombre d'éléments retenus.
 
Du coup, malheureusement, il ne faut pas s'arrêter à la première solution trouvée, mais tenter toutes les solutions (donc quand on a une solution, on doit repasser à la moulinette le bignou en introduisant une variante, jusqu'à épuisement de toutes les solutions).
Je dirais qu'il faut donc faire un glouton récursif, qui permet de tester chaque variante : pour chaque élément qui tient dans le sac, il faut tester la solution en le mettant dedans, et la solution en ne le mettant pas.

tu réfléchis 10s et tu t'aperçoit qu'il s'agit du problème dual du sac à dos

dual ?

bon, MB, tu vas repartir à la fac 1 ou 2 ans et tu reviendra discutetr sur les sujets d'algo merci

Excuse-moi Joel, mais avant d'être insultant et condescendant comme à ton habitude, file un lien qui explique "knapsak", moi je tombe sur le problème du sac à dos dans Wiki, et ce problème ne contient pas la partie en gras de la question d'eraser2k.
 
Alors explique au lieu de prendre les autres pour des cons, t'es tellement plus fort que tout le monde, que tu devrais faire partager ton immense savoir tu crois pas ?
 
Attitude de gros connard, comme d'habitude.
Bonne année.

Pareillement la bonne année bien sur hein

Ensuite, je répéte tu réfléchis 10s et tu t'aperçois que si tu prends le nombre d'entiers comme valeur à optimiser et non leur somme (qui est fixe) tu retombe sur un knapsak - d'ou ma remarque sur la notion de dual -
Après si tu sais aps ce que sais que le dual de quelquechose, tu wikipedize totu seul aussi un peu hein

Et bizarrement, le PO a su se débrouiller lui

Et une deuxieme couche

Le vrai probleme :
http://en.wikipedia.org/wiki/Subset_sum_problem

et je cite

"Subset sum can also be thought of as a special case of the knapsack problem."

Merci, ca fera 10 francs, n'oubliez pas le guide

oui, de ce que je comprends, parmi les algos sur la page de wiki, ça s'apparente au "multi-objectif" (y'a pas de "dual" dans la page).
mais cet algo, si je ne m'abuse, permet de travailler sur plusieurs objectifs, à partir de plusieurs propriétés des éléments eux-mêmes. du coup je ne vois pas de rapport direct avec le problème, étant donné que le nombre d'éléments n'est pas une propriété des éléments eux-même, mais une propriété de la solution trouvée.

 
Genre un problème ou il faut maximiser un truc tout en restant sous une borne peut se ramener à un problème de minimisation d'un autre truc tout en restant au dessus d'une borne si tu voit ce que j'veux dire. Ici la contrainte est une égalité avec la borne, et on minimise le nombre d'objets (soit le probleme dual d'un sac à dos ou l'on chercherais a remplir le sac completement, les objets ayant tous une valeur egale)
 
cf ce cours qui a l'air pas mal:  
http://www-lih.univ-lehavre.fr/~ba [...] cours1.pdf
 
Edit: grilled, boulot de merde

d'accord, donc c'est pas le multi (parcequ'avec le multi, je pigeais pas comment on pouvait retomber sur nos pattes)

Si vous préférez la recherche opérationnelle c'est votre choix, moi je préfère largement la roue fait maison fabriquée dans la cave.

 
Bah en même temps, on pourrai aussi préférer oublier tout ce qu'on a inventé depuis 2000 ans. Le bon sens c'est juste une heuristique pourrave, et plus ou moins irréalisable en fonciton des problèmes et de leur taille.

Oui et non.
 
Comme détailé dans l'article Wiki, étant donné que ce problème n'a pas toujours de solution, on peut aussi partir du principe qu'une solution "relativement bonne" peut être considérée comme optimale, après tout dépend du degré de satisfaction recherché.
 
L'exemple le plus évident, c'est sur les vieilles chaînes hifi : il y avait une fonction "copier un CD sur une K7".
=> On disait si c'était une K7 60 ou 90 minutes, et il se débrouillait pour remplir les deux faces de la K7 sans faire des trous trop grands en fin de piste.
 
La plupart du temps, parceque le CPU qui se trouve dans une chaîne hifi doit être aussi puissant que celui qu'il y a dans ma montre, les développeurs ne sont pas partis sur des algos trop complexes : de toute façon passé 5 tests ça aurait duré trop longtemps.
 
Donc un bête algo glouton lancé 2 ou 3 fois de suite permettait d'optenir parmis les 3 résultats trouvés quel était le plus optimal, ce qui était satisfaisant dans 99% des cas.
Mais j'ai un CD que je n'ai jamais pu copier via le système de ma chaîne hifi, mais qui, lorsque je le copiais à la main en arrangeant les pistes comme je voulais, tenait parfaitement : on n'a pas forcément besoin de trouver LA solution optimale, il suffit généralement de trouver une solution raisonablement bonne, mais cela peut avoir ses limites.
 
C'est pourquoi la solution "de bon sens" n'est pas forcément plus mauvaise je pense qu'une approche complexe du problème pour tenter de l'optimiser : il suffit de limiter sciemment le nombre de tentatives de résolution, en supposant qu'après X tests, on aura de toute façon une solution suffisament bonne.
 
Après, X peut être en dur, ou dynamique : j'arrête quand je trouve une solution qui me plaît.
 
Dans ce cas, la solution gloutonne, qui est très simple à mettre en oeuvre, peut s'avérer plus rapide qu'un algo complexe. Dans l'exemple d'une copie de CD sur K7, vu que de toute façon il n'y a pas de solution optimale, on se rend vite compte que ça sert à rien de se prendre la tête.
 
Après, s'il s'agit d'organiser l'agencement intérieur d'une fusée où chaque cm3 perdu coûte quelques millions d'euros, on peut sortir l'artillerie lourde, évidement.
 
Mais quand il s'agit de faire tenir des valises dans un coffre, on utilise machinalement l'algo glouton avec parfois plusieurs ittérations, et c'est plutôt rare qu'on vide 12 fois le coffre avant de tout faire tenir, où qu'on finisse par partir avec un coffre à moitié vide et les 2/3 des bagades restés sur le trottoir...
 
Après, je dis pas qu'il faut obligatoirement utiliser l'algo le plus basique, loin de là.
Mais le mieux est l'enemi du bien, et mise à part quand on a besoin, la recherche de la perfection n'est pas forcément la meilleure solution.
 
Combien de fois t'ouvres une page de code et tu passes 3 jours à comprendre comment marche une routine alors que ça tiens en 3 lignes quand on se prends pas la tête ?
Ou là fois où une stagiaire qui bossait avec moi est restée bloquée une semaine entière sur une liste déroulante dans une page HTML parcequ'elle n'arrivait pas à implémenter un quicksort en JavaScript pour ordonner les lignes "mais putain, dans la lib que je t'ai fillé y'a un tri à bulle, pour 20 lignes affichées dans la liste tu vas pas me dire que ton quicksort va changer quelquechose bordel ! "

je crois que la vous êtes irrécupérables :|.

Après j'y peut rien si tes colalborateurs sont des tanches

MagicBuzz > On est d'accord, c''est une heuristique et on peut toujours utiliser des heuristiques. J'ai ajouté "pourrave" dans le sens ou tu ne connais pas forcément les limites d'une telle heuristique.
 
Le monsieur OP désirant connaitre la meilleure solution, c'est un peu naze de répondre qu'il faut faire à l'arrache non ?
 

   c'est le fond de ma pensee egalement.