Bonjour a tous,
le probleme que j'ai a soumettre ici relève plus de l'algorithmique que de la programmation, je n'ais pas pus trouver une solution je demande de l'aide.
En fait il s'agit d'un probleme de partage de monnaie.
On veut partager de la monnaie (1£, 2£, 3£, 5£, 100 £, ...) a 2 personne, de tel sorte que chacun ait le meme nbre de (piece ou billet), et que la difference entre la somme que possède les deux soit minimales.
Ex: si on a les pieces suivantes (1£, 1£, 3£, 5£, 100£, 10£)
p1=1£, 1£, 100£;
p2=3£, 5£, 10£;
donc la difference minimale est : (102-18)=84£.

Svp si vous pouvez quand meme me proposer quelque chose ,...
Merci

Là j'ai une solution qui me vient naturellement, mais sans doute pas la plus rapide, tu parles d'optimisation dans ton titre, mais à aucun moment tu ne présentes ce que tu as déjà réalisé, dur d'optimiser du vide .. Enfin continuons :

Tu tries ton tableau de pièces, exemple :

{1£, 1£, 3£, 5£, 10£, 100£}.

Tu déclares tes deux tableaux, un par personne, et deux variables de type entier ( voir réels si on va jusqu'aux cents ) qui serviront à compter la somme ( initialisée à 0 ).

Ensuite, tu fais une itération sur ton tableau ( on doit avoir le même nombre de pièces, donc on part du principe que la propriété longueur de notre tableau est toujours paire ). Et là, à chaque tour tu fais ta condition, si somme1 < somme2 ET tab1.longueur() < pieces.longueur()/2.

En gros, si la somme d'une personne est inférieure à celle de l'autre, et que celui ci a recu moins de la moitié des pieces, tu lui en donnes une, dans tous les autres cas, c'est l'autre qui recoit.

Pour le tri, certaines Collection de java.util en proposent, sinon regarde du côté du tri à bulles, ou tri fusion, qui sont deux algorithmes qu'on trouve facilement, et qui donc sont vite implémentés.

askerat > Bonne idée, mais il faudrait parcourir le tableau du plus grand élément au plus petit, donc dans un sens trié inverse.


Sinon résoudre le problème par contraintes, mais c'est un peu chercher loin ...

Merci, askerat pour ta proposition, mais je l'avais déjà testée mais, elle ça ne marche pas.
La preuve:
Ensemble : {2000£, 1000£, 7£, 6£, 5£, 4£, 3£, 2£}
si j'utilise ta solution j'obtient :
t1= [2000,6,4,2];
t2= {1000,7,5,3};
l'ecart est 997

alors que la solution doit être:
t1= {2000,4,3,2};
t2= {1000,7,6,5};
ecart =991.
Merci a tous ceux qui veulent bien y repondre.

Voilà un code provisoire pour faire faire ce que tu souhaite. Je suppose que le tableau est trié dans l'ordre croissant. Cependant nous pouvons faire beaucoup mieux...

public static int[][] division(int[] tableau) {
        if (tableau.length % 2 != 0) {
            return null;
        }

        int dispertion[][] = new int[2][tableau.length / 2];
        int somme[] = new int[2];


        for (int i = 0; i < somme.length; i++) {somme[i]=0;}
        
        int iterator = 0;
        int min = 0;
        int max = tableau.length - 1;
        int sommeMax = 1;
        int nombre = 0;
        while (iterator < tableau.length) {

            if (somme[iterator % 2] >= sommeMax) {
                nombre = tableau[min];
                min++;
            } else {
                nombre = tableau[max];
                max--;
            }

            if( somme[iterator % 2]+nombre >= sommeMax )
            {
                sommeMax = somme[iterator % 2]+nombre ;
            }

            somme[iterator % 2] += nombre;
            dispertion[iterator % 2][((iterator-(iterator%2))/2)] = nombre;

            ++iterator;
        }

        return dispertion;
    }

    public static void main(String agrs[]) {
        int tableau[] = new int[]{2, 3, 4, 5, 6, 7,10,10, 1000, 2000};

        int[][] result = division(tableau);

        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                System.out.print(result[i][j] + " | ");
            }
            System.out.print("\n");
        }

    }

déjà merci damdam pour le code exemple, mais il ya encore un bug, car celle là aussi j'y ai pensé et j'ai été bloqué par cet exemple:

p= {37,100,500,800,1444,2000,2000,2000,2000,2000}

selon ton exemple on obtient:
p1={2000,37,2000,1444,800}=6281
p2={2000,2000,2000,100,500}=6600
ecart=319

et pourtant la solution optimale serait:
p1={2000,2000,1444,800,100}=6344
p2={2000,2000,2000,500,37}=6537

ecart=193

Je viens de modifier le code légèrement est j'obtient le bon résultat pour le 2nd cas.

public class Main {

    public static int[] sort(int[] data)
    {
        for(int i=0;i<data.length;i++)
        {
            for(int j=i;j<data.length;j++)
            {
                if(data[i]>data[j])
                {
                    int tmp = data[j];
                    data[j] = data[i] ;
                    data[i] = tmp ;
                }
            }
        }
        return data ;
    }

    public static int[][] division(int[] tableau) {
        if (tableau.length % 2 != 0) {
            return null;
        }
        tableau = sort(tableau);

        // Permet de stocker la distribution des pièces
        int dispertion[][] = new int[2][tableau.length / 2];
        // Permet de stocker la somme totale distribué 
        int somme[] = new int[2];


        for (int i = 0; i < somme.length; i++) {somme[i]=0;}
        
        int iterator = 0;
        int min = 0;
        int max = tableau.length - 1;
        int nombre = 0;
        while (iterator < tableau.length) {

            if (somme[iterator % 2] > somme[(iterator+1) % 2]) {
                nombre = tableau[min];
                min++;
            } else {
                nombre = tableau[max];
                max--;
            }

            somme[iterator % 2] += nombre;
            dispertion[iterator % 2][((iterator-(iterator%2))/2)] = nombre;

            ++iterator;
        }

        return dispertion;
    }

    public static void main(String agrs[]) {
        int tableau[] = new int[]{37,100,500,800,1444,2000,2000,2000,2000,2000};

        int[][] result = division(tableau);

        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                System.out.print(result[i][j] + " | ");
            }
            System.out.print("\n");
        }

    }
}

Je te remercie une fois de plus pour ton devouement , mais comme on le dit un programme n'est jamais parfait:

regarde ces valeurs:
P= {1211, 821, 1292, 153, 269, 694, 814, 1622, 93, 1091, 1760, 700, 730, 368, 408, 1548, 1233, 611, 1104, 683, 1379, 1135, 194, 1763,1578,280,415,981,425,1685,505,1635,505,1796,139,1126,489,953,747,933};

Il ya 40 valeurs.
Mais l'écart minimal ici est de 0.

Ton code lui renvoie un écart plus grand (210);

Merci déjà pour ce que tu as fait.

Problème identique a celui ci :

http://www.siteduzero.com/forum-83-351 [...] ntainers.html

Mais je n'ai pas encore trouvé de solution acceptable... Donc si quelqu'un trouve une solution (inferieure en complexité a l'énumération complète, qui est factorielle), I'll be happy

effectivement flooder c'est le meme type de probleme, je dois avouer qu'il est serieux ce probleme.

Je viens de continuer la recherche d'un algorithme. Pour le moment, j'arrive à un écart de 2 sur le dernier tableau.
Si tu trouve une solution optimale merci de me MP ou voir poster ici...

heuu ben sinon il y'a moyen de travailler différemment ...
On distribue les valeurs aux deux aléatoirement ... (on bien avec votre premier algorithme )
On classe les deux tableau par ordre croissant (pas obligatoire mais plus rapide par la suite)
On prend le premier chiffre du premier tableau et on le compare avec tous les chiffre de l'autre tableau (un par un ) si en les inversant on fait diminuer l'écart entre les deux tableau, on les inverses. Sinon on essaye le chiffre suivant dans le premier tableau

On s'arrête lorsque on ne trouve plus deux nombre qui font diminuer l'écart

Citation : Snooooopy

heuu ben sinon il y'a moyen de travailler différemment ...
On distribue les valeurs aux deux aléatoirement ... (on bien avec votre premier algorithme )
On classe les deux tableau par ordre croissant (pas obligatoire mais plus rapide par la suite)
On prend le premier chiffre du premier tableau et on le compare avec tous les chiffre de l'autre tableau (un par un ) si en les inversant on fait diminuer l'écart entre les deux tableau, on les inverses. Sinon on essaye le chiffre suivant dans le premier tableau

On s'arrête lorsque on ne trouve plus deux nombre qui font diminuer l'écart

Effectivement cette solution parraisait comme toujours la bonne mais il ya une erreur en testant sur le dernier cas posté ici.

pourtant ils sont tout deux obligé d'avoir le même nombre de pièce =/
je vais en vitesse essayer
une autre solution serait d'essayer toutes les combinaisons possible ...
la au moins tu es sur d'avoir la bonne =/

Ne te fatigue pas j'ai déjà essayé

bon mon code renvois un écart de -1 ( 1 en val absolue ^_° )

public static void main(String args[]){
     
     int[] P = {1211, 821, 1292, 153, 269, 694, 814, 1622, 93, 1091, 1760, 700, 730, 368, 408, 1548, 1233, 611, 1104, 683, 1379, 1135, 194, 1763,1578,280,415,981,425,1685,505,1635,505,1796,139,1126,489,953,747,933};
     Trie(P);
     
    }
  public static void Trie(int[] tab){
    if(tab.length%2 !=0 ){System.err.println("erreur ");}
      int[] tableau1 = new int[tab.length/2];
      int[] tableau2 = new int[tab.length/2];
      for(int i = 0; i<tab.length/2;i++){
         tableau1[i] = tab[i]; 
         tableau2[i] = tab[i+tab.length/2];
        }
      int équart = sumTab(tableau1)-sumTab(tableau2);
    int chgmnt_equart=0;
    int tempchgmnt=0;
    int changetemp;
    do{
        tempchgmnt=0;
        chgmnt_equart=0;
         for(int i = 0; i<tableau1.length && chgmnt_equart==0;i++){ 
                for(int j=0;j<tableau2.length && chgmnt_equart==0;j++){
                    tempchgmnt = tableau1[i]-tableau2[j];
                    //  si ils sont de signe différents
                    if(tempchgmnt*équart <0){
                       // si l'équart obtenus en valeurs abolue < enciens équart
                       if(Math.abs(tempchgmnt+équart) < Math.abs(équart)){
                        changetemp = tableau2[j];
                        tableau2[j] = tableau1[i];
                        tableau1[i]=changetemp;
                        
                        équart=tempchgmnt+équart;
                        }
                    }
                }
            }
    }while (chgmnt_equart!=0);
    System.out.println( équart);
      
    }
  public static int sumTab(int[]tab){
     int returne =0;
      for (int i =0;i<tab.length;i++){
         returne = returne + tab[i];
        }
     return returne;
    }
    }

Mais il est censé renvoyer un ecart de 0 j'ai verifié avec un autre code (trop compliqué ).

Je voulais aussi adopté la methode "brute force" en esayant toutes les possiblités au moins on est sur que ça marchera, mais je ne vs pas trop coment y inclure de la recursivité
Chui vraimen pommé sur ce coup là

Citation : willykonguem

Merci, askerat pour ta proposition, mais je l'avais déjà testée mais, elle ça ne marche pas.
La preuve:
Ensemble : {2000£, 1000£, 7£, 6£, 5£, 4£, 3£, 2£}
si j'utilise ta solution j'obtient :
t1= [2000,6,4,2];
t2= {1000,7,5,3};
l'ecart est 997

alors que la solution doit être:
t1= {2000,4,3,2};
t2= {1000,7,6,5};
ecart =991.
Merci a tous ceux qui veulent bien y repondre.

Tu as mal lu alors, car ma solution donne bien :

t1= {2000,4,3,2};
t2= {1000,7,6,5};

Tu donnes tjs à celui qui en as le moins, et il en recoit maximum la moitié. Et effectivement, comme le souligne olivier, il faut le parcours de length - 1 à 0, ou alors le trier en ordre inverse.

Meme sur le dernier cas ta solution ne marche pas, essaie de verifier tous les cas posté ici avant de faire des affirmations

Il existe une solution à ce probleme, malheureusement je ne me souvient plus du nom de l'algo :/
De plus cette solution est de l'ordre n^m : en O(n^m) avec m nombre de termes( et il y a une recompense pour celui qui trouve une solution en O(n^x) avec x une constante, je crois ^^.)

Le principe de l'algo :
Dans le cas on l'ecart est de 0.
prendre une matrice de booléen initialisé à FAUX de largeur egale à la somme de tous les termes et de hauteur egales au nombres de termes.
initialisé la premier ligne en mettant la case correspond au premier terme à VRAI. (exemple si c'est 3, toutes les cases de la premier ligne seront à FAux, sauf celle d'indice 3)
ensuite pour chaque ligne :
prendre le terme correspondant à l'indice de la ligne, et mettre ça position à vrai.
parcourir la ligne precedente et reporter tous les cases à VRAI sur la ligne en cour ET (si la case est VRAI) mettre la case à l'indice i + terme à vrai.
exemple :
(3, 2)
ligne 1 : FFVFF
ligne 2 : FFVVV

une fois la matrice complet, il va falloir extraire les solutions.

pour cela, on calcule la valeur que l'on desir ( si la moitie de la somme totale)

// debut methode //
puis on regarde si la case à cette indice est vrai sur la derniere ligne, sinon il n'y a pas de solution (avec un ecart de 0)

SI elle est VRAI :

on regarde si la case juste au dessus est vrai, si c'est le cas on rapelle la methode sur cette ligne, en cherchant toujours la meme valeur.
apres (que la condition precedente soit vrai ou fausse) on regarde si la case à l'indice : (valeur recherché) - (valeur du terme correspondant à la ligne) est vrai, si c'est la cas on memorise le terme ( ça à toi de te debrouiller ) et on appelle la methode sur la ligne precedente mais avec comme valeur recherchée : (valeur recherchée) - (terme de la ligne)

si la valeur recherche est egal à 0, c'est que tu as une solution ! Mais ! il faut regarder le nombre de terme pour savoir s'il est egale à la moitié du nombre de terme ^^.




Si il n'y a pas de solution (case sur la derniere ligne = à FAUX, ou pas de la bonne longueur) tu fais une recherche sur le terme recherché - 1 puis + 1 si il n'ya pas de solution, puis -2, +2 .... jusqu'a avoir une solution (ou pas ^^)

bon l'algo n'est pas simple et j'espere mettre fait comprendre ( et que mes souvenir soit bon) mais c'est la methode optimum pour trouver la Meilleur solution.
Apres il y a quelque soucis : taille de la pile d'appel, et de la matrice (mais avec des pieces il n'y pas trop de risque)

Malhomar , je n'ai toujours rien compris a ce que tu as dit
je te rappelle que l'on veut trouver l'écart minimal pas savoir si existe un ecart en 0 ou pas.
S'il te plait, quand tu expliques il faut utiliser des exemples précis.

Exemple: p={1,3,9,10}

Merci

Cet algo ne repond malheureusement pas a l'ennoncé, il donne la solution pour un nombre quelconque de pieces de chaque coté et non pas un nombre fixe (a moins d'explorer chacune des solutions, mais a mon avis c'est une mauvaise idée)

Mais sinon, en effet, c'est plutot pas mal.

avec p={1,3,9,10}
Somme = 23

Matrice :

0 1       5         10        15        20    23
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1

Les sommes qu'il est possible de faire avec p sont donc :
1, 3, 4, 9, 10, 11, 12, 13, 14, 19, 20, 22, 23

Hop voilà un petit exemple pour le brute force. Il trouve la solution optimale.

Par contre l'algorithme est en temps non polynomial (NP).

Il y a sans doute moyen d'optimiser certaines parties, don la parti que j'ai noté. Utiliser des tableaux au lieu de linked list doit sans doute améliorer aussi.

Prévoir un peu de temps pour les grands tableaux p ...

import java.util.Iterator;
import java.util.LinkedList;

public class Main {

	
	public static int bestScore = 0;
	public static Node bestSolution = null;
	
	public static void main(String args[]){
	     
	    //int[] p = {1211, 821, 1292, 153, 269, 694, 814, 1622, 93, 1091, 1760, 700, 730, 368, 408, 1548, 1233, 611, 1104, 683, 1379, 1135, 194, 1763,1578,280,415,981,425,1685,505,1635,505,1796,139,1126,489,953,747,933};
	    int[] p = {37,100,500,800,1444,2000,2000,2000,2000,2000}; 
		trie(p);
	     
	}
	
	public static void trie(int[] tab) {
		LinkedList<Integer> l = new LinkedList<Integer>();
		for( int i = 0; i< tab.length; i++) l.add(tab[i]);
		Node node = new Node();
		findRecursif(l,node);
		System.out.println("Aucune solution n'a été trouvée");
		System.out.println("Best solution : "+bestSolution.sum1+ " "+bestSolution.sum2);
	}
	
	public static void findRecursif(LinkedList<Integer> tab, Node node) {
		if (tab.size()>0) {
			/* Possible optimisation debut*/
			Node node1 = new Node();
			node1.duplicate(node);
			Node node2 = new Node();
			node2.duplicate(node);
			Integer i = tab.remove(0);
			node1.tab1.add(i);
			node1.sum1 += i;
			node2.tab2.add(i);
			node2.sum2 += i;
			/* Possible optimisation fin*/
			findRecursif(createCopy(tab), node1);
			findRecursif(createCopy(tab), node2);
		} else {
			// Solution reached
			if (node.tab1.size() == node.tab2.size() && (Math.abs(node.sum1-node.sum2)<bestScore || bestSolution == null)) {
				bestSolution = node;
				bestScore = Math.abs(node.sum1-node.sum2);
				if (node.sum1 == node.sum2) {
					System.out.println("A Good solution has been found : "+node.sum1+" "+node.tab1.size()+" elements each");
					//Print ce que tu veux
					System.exit(0); // Barbare
				}
			}
		}
	}
	
	public static LinkedList<Integer> createCopy(LinkedList<Integer> l) {
		LinkedList<Integer> ret = new LinkedList<Integer>();
		Iterator<Integer> it = l.iterator();
		while(it.hasNext()) ret.add(it.next());
		return ret;
	}
	
	public static class Node {
		public LinkedList<Integer> tab1 = new LinkedList<Integer>();
		public LinkedList<Integer> tab2 = new LinkedList<Integer>();
		public int sum1;
		public int sum2;
		
		public void duplicate(Node node) {
			Iterator<Integer> it = node.tab1.iterator();
			while(it.hasNext()) {
				this.tab1.add(it.next());
			}
			it = node.tab2.iterator();
			while(it.hasNext()) {
				this.tab2.add(it.next());
			}
			sum1 = node.sum1;
			sum2 = node.sum2;
		}
	}
}

Une enumeration complete n'est pas une solution viable, il y a <math>\(C_n^{2n}\)</math> possibilités (avec 2n le nombre total de pieces)...

Ce qui donne comme possibilités :
n = 1 : 1
n = 5 : 252
n = 10 : 184.756
n = 20 : 134.10^9 (134 milliards)
n = 30 : 118.10^15
...

Ceci dit, on pourrait ameliorer la solution de maholmar, en ne stockant pas dans la matrice un booleen, mais une liste du nombre de coups differents qui nous permettent d'y parvenir (plutot facile a réaliser).

Ca donnerai la matrice suivante sur l'exemple p={1,3,9,10}

0  1            5           10                 15           20        23
0 (1) 0  0   0  0 0 0 0  0   0   0   0   0   0  0 0 0 0  0   0  0  0   0

0 (1) 0 (1) (2) 0 0 0 0  0   0   0   0   0   0  0 0 0 0  0   0  0  0   0

0 (1) 0 (1) (2) 0 0 0 0 (1) (2)  0  (2) (3)  0  0 0 0 0  0   0  0  0   0

0 (1) 0 (1) (2) 0 0 0 0 (1) (1) (2) (2) (3) (3) 0 0 0 0 (2) (3) 0 (3) (4)
                            (2)         (2)

Les combinaisons possibles avec 2 pieces sont donc 4, 10, 11, 12, 13 et 19.

Etant donné qu'on peut passer d'une ligne a une autre grace a une simple addition (et un decalage) de la ligne precedente, on a un algo en complexité temporelle egale a O(n*s) et de complexité spatiale : O(n²*s) au pire, si on garde les solutions, O(n*s) sans les garder (en travaillant toujours sur la même ligne)

Cette solution est envisageable mais tu a pensé a la quantité de mémoire utilisé ?
La complexité en ce moment dépend des valeurs des pièces
Ex: si on a p={1000000,3000000,2000000,1000000}
on vat creer un tableau de dimension
4*7000000=28000000 Octet de mémoire = 26 Mo de mémoire seleument pour le stockage du tableau et son parcours je n'y pense meme pas.

En effet, c'est un problème si les valeurs des pieces sont très grandes, je pense qu'une limite raisonnable serrait que la somme totale des pieces ne depasse pas 10 millions.

Maintenant, en prenant 200 pieces de valeurs inferieures a 2000, ca ne fait un tableau que de 4.000.000 d'int au maximum, soit exessivement peu comparativement aux 9.10^58 combinaisons possibles d'une enumeration complete.

Et parcourir un tableau de 4 millions de cases, c'est assez rapide

Moi je reflechie toujours sur l'enumération complete mais mon objectif étant d'annuler a la base certain cas que je jugerait irrealisable.
Question de diminuer le nombre d'iteration.

le hic c'est que tu peux pas les éliminé sans avoir vus la différences entres les 2 classes ....
HA SI il y'a moyen
tu peux faire ton premier algorithme et ça te donne une idée d'équart mais surtout ça te donne deux valeurs

j'ai nommé : la somme des valeurs du vecteurs 1 (SumVect1):)
et la somme des valeurs du vecteurs 2 (SumVect2):)
durant le brute force si a un moment donné la somme des valleurs d'un des vecteurs dépasse max(SumVect1,SumVect2); c'est qu'il y'a une solution plus optimale donc pas la peine de continuer

bien sur des qu'on a trouvé une solution avec un écart plus petit,
on recalcule "SumVect1" et "SumVect2" de façons a limiter encore plus



en optimisant un peu (je pense récursif )
tu peux t'arranger pour skipper tt d'un coup si mar exemple max((SumVect1),(SumVect2)) = 300
vecteur1 ={100,200,?,?,?}
tu skippes tous les vecteurs qui commencent par {100,200 d'un coup sans refaire le calcul 20 000 fois

de plus si tu as trié tes vecteurs et que tu fais les test par "ordre croissant" (le premier chiffre du vecteur => que celui du vecteur précédent (ext pour les chiffres suivant))
tu sais skipper tous les chiffres suivants à partir du moment ou tu l'as dépassé une fois
je pense à


valeur limite : 300;

{200, 50, 3, 1,2} ok
{200,100,???} false
tous les vecteurs suivant sont mauvais parce que a chaque fois le 2eme nombre est > 100
{200,?(>=100),??}false

Tu a tout a fait raison, voilà une pensée a laquelle on avait pas pensé, merci snoopy,
je vais regarder cela ce soir, en attendant si quelqu'un parvient a optimiser encore mieux, ce serait toujours une bonne idée de le poster ici.

Merci encore a tous.

Salut, a tous, j'ai trouver une manière de resoudre le problème. Et si on utlisait la méthode de resolution du problème du sac a dos.
Ceci est très plausible.