Discussion :

[zwan.bourg]

Bonjour à tous,
Je viens de passer plus de cinq heures sur ce probleme auquel je trouve pas de solution satisfaisante.
J'ai un tableau a 2 dimensions disons n lignes et m colonnes.
Je veux faire des combinaisons afin en choisissant un élément par colonne au fur et a mesure que je parcours les lignes du tableau de haut en bas.
Je dois faire des sommes pour chaque combinaison possible et trouver la plus grande somme.
Ex: si le tableau a 2 lignes et 3 colonnes, on a les sommes suivants (lxcy veut dire ligne x colonne y):

• l1c1+l2c1
• l1c2+l2c1
• l1c3+l2c1
• l1c1+l2c2
• l1c2+l2c2
• l1c3+l2c2
• l1c1+l2c3
• l1c2+l2c3
• l1c3+l2c3

Pour un tableau, n * m, on a donc m puissance n differentes sommes (je pense)
Pouvez-vous m aidez? je pense que ça doit etre banal mais je trouve pas le chemin!
Je comprends les langages suivants: C#, Java, Javascript, PHP, VB, C/C++

[Beginner.]

Bonjour,

Je débute mais j'aimerais comprendre ton problème, est-ce que tu sais déjà comment faire toutes les sommes ? Si oui pourquoi ne pas ensuite mettre toutes ces sommes dans un tableau et ensuite chercher la somme maximum.

Ensuite on retrouverait le numéro de la ligne et de la colonne à partir de l'indice du maximum.

Bien sûr cela suppose de faire le calcul de toutes les sommes dans un ordre précis (ordre du comptage dans la base concernée).

Tu vois ce que je veux dire ou pas ?

[zwan.bourg]

Salut,
Justement mon probleme c'est comment faire les sommes! Sinon pour les comparaisons, je peux m en sortir.
Ici, j ai donné un exemple 2 * 3 mais le tableau est supposé estre plus grand et on peut se retrouver facilement avec des millions de cheminements possibles.

[Trap D]

Si j'ai bien compris le problème, il me semble que la plus grande somme se fera avec le plus grand élément de la première ligne, le plus grand élément de la seconde ligne etc, etc, non ?

[zwan.bourg]

Non c'est pas tout à fait exact.
Je veux la combinaison qui aura la plus grande somme. Un élément dans la 1ere ligne + un second dans la 2e ligne + ... En fait un element dans chaque ligne jusqu'a la derniere ligne.
C'est pour cette raison que je cherche a faire les sommes de chaque combinaison possible.
Mon probleme reste une methode qdequate pour parcourir le tableau

[kwariz]

Hello, Trap D a raison. Si tu prends exactement un élément par ligne, sans autres contraintes, la somme sera maximum si tu prends le max de chaque ligne.

[zwan.bourg]

Oh C'est vrai ça! Mais ça ne resoud toujours pas le probleme car j'ai aussi besoin de certaines des sommes classées par ordre pour d'autres traitements.
Mais merci deja, "penser autrement" peut peut-etre m aider.
Je vais reflechir à cela et si vous avez des idées n'hesitez pas...

[Trap D]

Le problème est de savoir de combien de sommes tu as besoin !
Car dans ce genre de problème, tu n'as besoin de considérer que "l'instant présent" en considérant qu'à l'indice i tu connais tout de dont tu as besoin, (c'est à dire que le problème est résolu pour l'indice i - 1)
Comment calculer les nouvelles sommes de l'indice i.
A mon avis, et c'est la que le problème se pose (...) tu devrais ordonner les elements de ta ligne par ordre décroisssant, et calculer les nouvelles sommes à partir des anciennes en tenant compte des écarts entre les sommes précédentes et les nombres de la ligne en cours.

Je reviens maintenant à : c'est à dire que le problème est résolu pour l'indice i - 1)
Ben oui, pour l'indice 0 c'est tout simplement les nombres ordonnée par ordre décroissant !

[Beginner.]

Salut,
Justement mon probleme c'est comment faire les sommes! Sinon pour les comparaisons, je peux m en sortir.
Ici, j ai donné un exemple 2 * 3 mais le tableau est supposé estre plus grand et on peut se retrouver facilement avec des millions de cheminements possibles.

Pour la somme max la solution a été donnée et pour le calcul de toutes les sommes je voulais savoir si le fait de fixer le nombre de ligne à 2 posait problème ? Je pense que quelque soit le tableau on peut insérer toutes les valeurs dans un tableau de 2 lignes et fixer le nombre de colonne à la valeur nécessaire ou bien ça pose problème ?

J'ai fait quelque chose qui à l'aire de fonctionner je crois mais la gestion des lignes pour éviter les répétions, lorsque qu'on a N lignes comment éviter de calculer par exemple l3c1 + l1c1 si on a déjà calculé l1c0 + l3c1 ?

En gros si on a N lignes comment trouver tous les couples possibles LiLj en excluant les cas où i=j et aussi en évitant par exemple de comptabiliser l3l4 si on a déjà comptabiliser l4l3...

EDIT :

Pour un tableau, n * m, on a donc m puissance n differentes sommes (je pense)

J'étais parti sur ce nombre que tu suggères, c'est-à-dire nbrColonne ^ nbrLigne surtout que ça marche au début : 2^3 = 9 c'est ok et 3^3 = 27 c'est aussi ok mais apparemment par exemple ça marche pas pour 3^4 = 81 avec mon code je trouve 54 possibilités mais je ne sais pas si il est bon...

En fait je crois que ta formule marche dans les cas où on a deux lignes d'ailleurs j'étais parti sur cette base...

Finalement je trouve cette formule : nbrP = 0.5*nbrligne*(nbrligne - 1)*nbrColonne^2.

Qu'en pensez-vous ? Pas facile en tous cas...

[Beginner.]

Rebonsoir,

Voici une tentative de débutant de code en java qui effectue toutes les sommes, celles-ci ne sont pas sauvegardées mais elles sont toutes accessibles avec les indices des lignes et colonnes des termes 1 & 2 additionnés, l'endroit où le code de sauvegarde doit être placé est indiqué en commentaire... La valeur max n'est pas calculée, il y a plusieurs solutions pour cela dont une a été donnée... Enfin bref j'ai juste mis ce qui te manquait c'est-à-dire comme tu le dis toi-même : " Mon probleme reste une methode qdequate pour parcourir le tableau ".

Je ne sais pas si il est correct :

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
33
34
35
36
37
38
39
40
41
 
public class CalculeSommes {
 
    /**
     * @param args
     */
    public static void main(String[] args) 
    {
        // TODO Auto-generated method stub
 
        int nbrColonne = 3;
        int nbrLigne = 2;        
        int indicenbrDeValeurs = 0 ;      
 
        int TabDeValeurs[][] = new int [nbrLigne][nbrColonne] ; // tableau de tous les termes
        for (int i = 0 ; i < nbrLigne ; i++)                    // rempli le tableau avec des valeurs quelconques...
            for (int j = 0 ; j < nbrColonne ; j++)  
                TabDeValeurs[i][j] = 2 + i + 3*j ;
 
       System.out.println ("Résultat pour " + nbrLigne + " lignes et " + nbrColonne + " colonnes (" + (0.5 * (nbrLigne - 1) * nbrLigne * nbrColonne * nbrColonne) + " possibilités) :") ; System.out.println ("") ;
 
 
        for (int indiceligneTerme1 = 0, indiceligneTerme2 = 1 ; indiceligneTerme1 < nbrLigne-1 ; indiceligneTerme2++) 
        {                                                
            for (int indicecolonneTerme1 = 0, indicecolonneTerme2 = 0 ; indicecolonneTerme1 < nbrColonne ; indicecolonneTerme2++, indicenbrDeValeurs++)
            {
                int S = TabDeValeurs[indiceligneTerme1][indicecolonneTerme1] + TabDeValeurs[indiceligneTerme2][indicecolonneTerme2];
 
                System.out.println ("L" + indiceligneTerme1 + "C" + indicecolonneTerme1 + " + L" + indiceligneTerme2 + "C" + indicecolonneTerme2 + " ---> Somme" + (indicenbrDeValeurs + 1) + " = " + S) ;
                // c'est ici qu'il faut rajouter le code pour stoker la somme avec les indices des lignes et colonnes des termes 1 & 2 additionnés                
 
                if (indicecolonneTerme2 == (nbrColonne - 1)) {indicecolonneTerme2 = -1 ; indicecolonneTerme1++ ; System.out.println ("");}
            }
 
            if (indiceligneTerme2 == (nbrLigne - 1)) { indiceligneTerme1++ ; indiceligneTerme2 = (nbrLigne - indiceligneTerme1-1) ; System.out.println ("");}
 
        }
 
    }
 
}

Résultat pour 2 lignes et 3 colonnes (9.0 possibilités) :

L0C0 + L1C0 ---> Somme1 = 5
L0C0 + L1C1 ---> Somme2 = 8
L0C0 + L1C2 ---> Somme3 = 11

L0C1 + L1C0 ---> Somme4 = 8
L0C1 + L1C1 ---> Somme5 = 11
L0C1 + L1C2 ---> Somme6 = 14

L0C2 + L1C0 ---> Somme7 = 11
L0C2 + L1C1 ---> Somme8 = 14
L0C2 + L1C2 ---> Somme9 = 17

Résultat pour 2 lignes et 4 colonnes (16.0 possibilités) :

L0C0 + L1C0 ---> Somme1 = 5
L0C0 + L1C1 ---> Somme2 = 8
L0C0 + L1C2 ---> Somme3 = 11
L0C0 + L1C3 ---> Somme4 = 14

L0C1 + L1C0 ---> Somme5 = 8
L0C1 + L1C1 ---> Somme6 = 11
L0C1 + L1C2 ---> Somme7 = 14
L0C1 + L1C3 ---> Somme8 = 17

L0C2 + L1C0 ---> Somme9 = 11
L0C2 + L1C1 ---> Somme10 = 14
L0C2 + L1C2 ---> Somme11 = 17
L0C2 + L1C3 ---> Somme12 = 20

L0C3 + L1C0 ---> Somme13 = 14
L0C3 + L1C1 ---> Somme14 = 17
L0C3 + L1C2 ---> Somme15 = 20
L0C3 + L1C3 ---> Somme16 = 23

Résultat pour 3 lignes et 3 colonnes (27.0 possibilités) :

L0C0 + L1C0 ---> Somme1 = 5
L0C0 + L1C1 ---> Somme2 = 8
L0C0 + L1C2 ---> Somme3 = 11

L0C1 + L1C0 ---> Somme4 = 8
L0C1 + L1C1 ---> Somme5 = 11
L0C1 + L1C2 ---> Somme6 = 14

L0C2 + L1C0 ---> Somme7 = 11
L0C2 + L1C1 ---> Somme8 = 14
L0C2 + L1C2 ---> Somme9 = 17

L0C0 + L2C0 ---> Somme10 = 6
L0C0 + L2C1 ---> Somme11 = 9
L0C0 + L2C2 ---> Somme12 = 12

L0C1 + L2C0 ---> Somme13 = 9
L0C1 + L2C1 ---> Somme14 = 12
L0C1 + L2C2 ---> Somme15 = 15

L0C2 + L2C0 ---> Somme16 = 12
L0C2 + L2C1 ---> Somme17 = 15
L0C2 + L2C2 ---> Somme18 = 18


L1C0 + L2C0 ---> Somme19 = 7
L1C0 + L2C1 ---> Somme20 = 10
L1C0 + L2C2 ---> Somme21 = 13

L1C1 + L2C0 ---> Somme22 = 10
L1C1 + L2C1 ---> Somme23 = 13
L1C1 + L2C2 ---> Somme24 = 16

L1C2 + L2C0 ---> Somme25 = 13
L1C2 + L2C1 ---> Somme26 = 16
L1C2 + L2C2 ---> Somme27 = 19

[zwan.bourg]

Cool ton aide.
En ce qui concerne le nombre de lignes, je ne peux vraiment pas decider (ni pour les colonnes d'ailleurs) je reçois le tableau en entrée (comme donnée).
Je vais voir si au niveau de ton code, ta logique peut m aider. (au dela de 2 lignes bien sur)
Merci, je vous fait un retour dans la semaine! Il faut profiter du Dimanche

[Beginner.]

Cool ton aide.
En ce qui concerne le nombre de lignes, je ne peux vraiment pas decider (ni pour les colonnes d'ailleurs) je reçois le tableau en entrée (comme donnée).

Oui ok mais je me disais que tu pouvais récupérer toutes les données et les réarranger dans un tableau à deux lignes mais bon peu importe car finalement le code que j'ai mis accepte plus de deux lignes...

Merci, je vous fait un retour dans la semaine! Il faut profiter du Dimanche

Ok !