algo combinaison=somme Fermé

Question

Bonjour,

à tout hasard je demande... pour une petite application, il y a une bricole que j'aimerais ajouter mais je crois que l'ago est hors de ma portée.

on a une liste d'items ayant chacun un montant

il s'agit de suggérer les combinaisons de montants (chacun pouvant être représenté plusieurs fois) dont la somme est égale à un autre montant

l'application, pour éventuellement y voir plus clair, c'est qu'on tient un compte en banque, et à l'occasion d'un ajustement manuel du solde (genre d'après la tenue il doit y avoir 100 euros mais dans les faits il n'en reste que 25), proposer les possibles dépenses (parmi celle connues, genre il manque 86 centimes => on suggère une baguette) qu'on aurait oublié de comptabiliser.

Bon ce n'est pas essentiel, c'est un peu un luxe, mais bon j'aimerais bien l'ajouter mais je ne vois même pas comment attaquer le problème.

n'impotre quelle piste en pseudocode est bienvenue :)

merci!

modulo22 · Answer

items //valeures des items rangées dans l'ordre décroissant
resultat //nombres d'items utilisées initialisé à 0
maxresultat //nombres d'items utilisées maximum initialisé à l'infini
pos=items.length-2

void getItems(int reste){
   int position=0;
   int r=reste;
  while(r!=0){
   if(position==items.length){//reviens en arrière
     if(maxresultat[pos]==0)
       pos--;
     if(pos==-1)
      throw Impossibe();
     resultat[pos]--;
     maxresultat[pos]=resultat[pos];
     position=pos+1;
   }
   if(reste<items[position] || resultat[position]==maxresultat[position])
     position++;
   else{
   resultat[position]++;
   r-=items[position];
   }
}                                                           
--

%22

BE · Answer

C'est un peu tard peut-être ; j'ai fait cet algorithme ; on peut le trouver sur :
<https://code.google.com/archive/p/code4d/source
C'est écrit avec 4D SQL, mais je pense que c'est siffisamment lisible pour être compris et adapté.

Bonne chance

Algo combinaison=somme

2 réponses

Discussions similaires