Discussion :

[djamila]

salut,

J'ai posé déjà cette question mais je n'arrive pas a la retrouver alors je dois la reposer.

j'ai 4 chiffre A B C D et j'ai une valeur X qui a surement une relation avec les 4 chiffres ce qui veut dire:

X=A ou X=B ou X=C ou X=D ou
X=A+B ou X=A+C ou X=A+D ou X=B+C ou X=B+D ou X=C+D ou
X=A+B+C ou X=A+B+D ou X=A+B+D ou X=B+C+D ou
X=A+B+C+D

je cherche un algorithme pour le généraliser sur N valeur

SVP aidez moi, merci .

[b_reda31]

salut,

J'ai posé déjà cette question mais je n'arrive pas a la retrouver alors je dois la reposer.

j'ai 4 chiffre A B C D et j'ai une valeur X qui a surement une relation avec les 4 chiffres ce qui veut dire:

X=A ou X=B ou X=C ou X=D ou
X=A+B ou X=A+C ou X=A+D ou X=B+C ou X=B+D ou X=C+D ou
X=A+B+C ou X=A+B+D ou X=A+B+D ou X=B+C+D ou
X=A+B+C+D

je cherche un algorithme pour le généraliser sur N valeur

SVP aidez moi, merci .

Si je résume bien votre problème, vous recherchez les coefficients : a,b,c,d tel que :
X = aA+bB+cC+dD.
et a,b,c,d appartiennent à { 0 , 1 } (dans votre énumération vous n'avez pas cité X = 2A+B.)

En attendant de meilleurs réponses je vous propose celle-ci :
Générer l'ensemble des solutions possibles sous forme d'une matrice N colonnes, 2^N lignes (énumération exhaustive):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
Solution =
a   b   c   d
0   0   0   0
0   0   0   1
0   0   1   0
...
...
1   1   0   1
1   1   1   0
1   1   1   1

ensuite faire le test pour chaque ligne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
i=1;
Tant que (X!=X1) faire
   X1 = Solution[i,1]*A + Solution[i,2]*B + Solution[i,3]*C + Solution[i,4]*D 
   i = i+1;
FinTq;

Cependant cette solution est de complexité exponentielle de N. donc innenvisageable pour une valeur importante de N. Dans ce cas il faudrait peut-être voir du coté des algorithmes d'optimisation.

[Aleph69]

Bonjour,

comme b_reda_31 te le suggère, ton problème doit être soluble avec une méthode d'optimisation. Il s'agit de trouver les ensembles {a,b,c,d} inclus dans {0;1}^4 tels que a*A+b*B+c*C+d*D=X, la valeur X étant donnée (la généralisation à N valeurs est directe).

Par contre, je ne suis pas un expert en optimisation discrète mais ça ressemble beaucoup aux problèmes qu'on trouve en théorie des graphes ou en logistique. Peut-être avec la méthode du simplexe ou une variante?

[pseudocode]

J'ai posé déjà cette question mais je n'arrive pas a la retrouver alors je dois la reposer.

Subset sum problem

[djamila]

salut
voila mon problème avec d'autre manière:

j'ai des factures de N clients et chaque client a m factures non réglées. Un jours donné un (1) de ces clients vire dans mon compte (je ne connais pas qui est le client) un Montant X donné qui est peut être une facture ou la somme de plusieurs factures k. Je dois détailler les facture réglées pour savoir qui son on dette pour faire le suivi.

Alors sur N client je cherche les client qui ont ce montant X et chaque client a M factures non réglées alors
X=f1 ou f2 ou ..............fm ou f1+f2 ou f1+f3 ............. ou f1+f2+......+fm

Je veut dire je calcule toute les possibilité et j'affiche sur un tableau qui sont égales a X et je fais mon choix selon virement de la banque (le nom du client n'est pas clair sur le bon de versement ou sur un autre nom différent de ce que j'ai comme nom sur la table de mes clients ).

merci
djamila.

[pseudocode]

voila mon problème avec d'autre manière

Ca n'en reste pas moins le même problème (Subset sum problem).

[djamila]

salut

oui je sais mais tout est bon sauf la partie ou je calcule toutes les sommes possibles, je cherche un algorithme qui me facilite la tache de faire toutes les combinaisons possibles.

merci.

[pseudocode]

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// La liste des valeurs
int[] list = {12,75,21,108,46};
 
// la taille de la liste
int N = list.length;
 
// un compteur binaire
boolean[] choice = new boolean [N];
 
// pour chacune des 2^N valeurs du compteur binaire
int count = (int)Math.pow(2, N);
for(int k=0;k<count;k++) {
 
	// somme des valeurs pour lesquelles le bit du compteur binaire est à "1"
	int sum=0;
	for(int i=0;i<N;i++)
		if (choice[i]) sum+=list[i];
 
	// affiche l'opération effectuée et son résultat
	for(int i=0;i<N;i++)
		System.out.printf("%d*%d %s", choice[i]?1:0, list[i], (i<N-1)?"+ ":"");
	System.out.println("= "+sum);
 
	// incrémentation du compteur binaire
	for(int i=0;i<N;i++) {
		if (!choice[i]) {choice[i]=true; break;}
		choice[i]=false;
	}
 
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
0*12 + 0*75 + 0*21 + 0*108 + 0*46 = 0
1*12 + 0*75 + 0*21 + 0*108 + 0*46 = 12
0*12 + 1*75 + 0*21 + 0*108 + 0*46 = 75
1*12 + 1*75 + 0*21 + 0*108 + 0*46 = 87
0*12 + 0*75 + 1*21 + 0*108 + 0*46 = 21
1*12 + 0*75 + 1*21 + 0*108 + 0*46 = 33
0*12 + 1*75 + 1*21 + 0*108 + 0*46 = 96
1*12 + 1*75 + 1*21 + 0*108 + 0*46 = 108
0*12 + 0*75 + 0*21 + 1*108 + 0*46 = 108
1*12 + 0*75 + 0*21 + 1*108 + 0*46 = 120
0*12 + 1*75 + 0*21 + 1*108 + 0*46 = 183
1*12 + 1*75 + 0*21 + 1*108 + 0*46 = 195
0*12 + 0*75 + 1*21 + 1*108 + 0*46 = 129
1*12 + 0*75 + 1*21 + 1*108 + 0*46 = 141
0*12 + 1*75 + 1*21 + 1*108 + 0*46 = 204
1*12 + 1*75 + 1*21 + 1*108 + 0*46 = 216
0*12 + 0*75 + 0*21 + 0*108 + 1*46 = 46
1*12 + 0*75 + 0*21 + 0*108 + 1*46 = 58
0*12 + 1*75 + 0*21 + 0*108 + 1*46 = 121
1*12 + 1*75 + 0*21 + 0*108 + 1*46 = 133
0*12 + 0*75 + 1*21 + 0*108 + 1*46 = 67
1*12 + 0*75 + 1*21 + 0*108 + 1*46 = 79
0*12 + 1*75 + 1*21 + 0*108 + 1*46 = 142
1*12 + 1*75 + 1*21 + 0*108 + 1*46 = 154
0*12 + 0*75 + 0*21 + 1*108 + 1*46 = 154
1*12 + 0*75 + 0*21 + 1*108 + 1*46 = 166
0*12 + 1*75 + 0*21 + 1*108 + 1*46 = 229
1*12 + 1*75 + 0*21 + 1*108 + 1*46 = 241
0*12 + 0*75 + 1*21 + 1*108 + 1*46 = 175
1*12 + 0*75 + 1*21 + 1*108 + 1*46 = 187
0*12 + 1*75 + 1*21 + 1*108 + 1*46 = 250
1*12 + 1*75 + 1*21 + 1*108 + 1*46 = 262

[djamila]

salut le résultat affiché est ce que je cherche mais j'ai pas pu comprendre le code java. Ca fait quelque temps j'ai pas travaillé avec lui. Est-ce-que tu peux l'écrire sous forme algorithmique pour que je puisse le comprendre,

merci beaucoup

[djamila]

salut,

j'attends toujours ta réponse, si tu peux bien sur. J'ai pas pu comprendre la partie ou la valeur booléenne 0 devient 1 et le contraire.

est-ce que tu peux l'écrire si possible sous forme algorithmique, ou bien m'aider
pour le comprendre.

merci d'avance.

[pseudocode]

salut,

j'attends toujours ta réponse, si tu peux bien sur. J'ai pas pu comprendre la partie ou la valeur booléenne 0 devient 1 et le contraire.

Pour incrémenter une valeur binaire, il faut changer le premier bit "0" rencontré par un bit "1", et remettre à "0" les bits précédents.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
11100 --> 00010
   ^         ^

(Ici, j'ai représenté la valeur binaire de gauche à droite)

Ca peut donc se faire en une seule passe, en parcourant les bits du compteur et en remplacent les "1" par des "0", jusqu'a trouver le premier bit à "0".

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
FOR i = 1 TO N
  IF  bit[i] == 0 THEN
     bit[i]=1
     EXIT FOR
  ELSE
     bit[i]=0
  END IF
NEXT

[10_GOTO_10]

Ca n'en reste pas moins le même problème (Subset sum problem).

Plus exactement, c'est le problème du sac à dos (Knapsack Problem), le Subset sum problem n'en étant qu'un sous-ensemble (la somme à trouver est nulle).

Divers algorithmes sont proposés ici (dont celui proposé par pseudocode).

[djamila]

salut, désolé mais je n'ai toujours pas pu comprendre la liaison entre le code java et le résultat affiché, comment :

0 0 0 0 0 devient
1 0 0 0 0 et aprés
0 1 0 0 0
1 1 0 0 0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 0
1 1 1 0 0
0 0 0 1 0
. . . . . . . . etc

SVP aidez moi, je ne sais pas pourquoi quand j'exécute le code manuellement je ne trouve pas ce résultat.

Merci d'avance

[10_GOTO_10]

comment :
0 0 0 0 0 devient
1 0 0 0 0 et aprés
0 1 0 0 0
. . . . . . . .

C'est juste du binaire

00000 = 0
00001 = 1
00010 = 2
00011 = 3

[djamila]

salut,

"""C'est juste du binaire"""!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

ah ouiiiiiiiiiiii désolé maintenant je voi.

merci c tres gentil

[djamila]

salut,

"""C'est juste du binaire"""!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

ah ouiiiiiiiiiiii désolé maintenant je voi.

merci c tres gentil