Algorithme somme max à atteindre

Version imprimable

23/07/2012, 11h06
friedamichelle

Algorithme somme max à atteindre

J'ai une liste ou un tableau qui contient par exemple[0,8,25,45,...] trié,et un nombre par exemple 156.
Je cherche un algo qui me permettrait de déterminer quels sont les nombres que je dois enlever(les min possibles) à mon tableau pour la somme des nombres du tableau soient inférieure à 156
23/07/2012, 13h16
deathness

Le but de ce forum n'est pas de te donner la solution toute prête.

Et quel est ta difficulté sur cet algo? Qu'as tu déjà comme idée d'algo?

Un algo de type glouton sans subtilité est possible déjà.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int myfunction(int[] tab,int subTT) {
	int sum = 0;
	for (int i = 0; i < tab.length; i++) {
		 sum = sum + tab[i];
	}
	for (int i = 0; i < tab.length; i++) {
		if(sum-tab[i]<subTT){
			return tab[i];
		}
	}
	return sum;
  // il se peut la première boucle ne suffise pas pour trouver le nombre 
  // et qu'il faut soustraire deux nombres
}

J'ai trouvé cela comme le rendre plus général?

Code:

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
 
 
int[] myfunction(int[] tab, int subTT) {
		int sum = 0;
		for (int i = 0; i < tab.length; i++) {
			sum = sum + tab[i];
		}
		for (int i = 0; i < tab.length; i++) {
			if (sum - tab[i] < subTT) {
				int []returnTab = new int[1];
				returnTab[0] = tab[i];
				return returnTab;
			}
		}
 
		for (int i = 0; i < tab.length; i++) {
			for (int j = 1; j < tab.length; j++) {
 
				if(sum-(tab[i]+tab[j])<subTT){
 
					int []returnTab = new int[2];
					returnTab[0] = tab[i];
					returnTab[1] = tab[j];
					return returnTab; 
				}
 
			}
		}
		return null;
 
 
	}

23/07/2012, 16h54
Kearz
Soit j'ai pas compris le problème, soit tu n'y réponds pas du tout.

T'as bien un tableau t et tu veux que la somme de t soit inférieur à un entier x.
Si la somme des éléments t est supérieur à x tu retire des éléments du tableau jusqu'à ce que ça soit bon.
Le but est d'en retirer un minimum, de retourner le tableau et en plus le tableau est trié.

C'est ça?

Si c'est bien ça:

Tu récupère la somme du tableau, donc pour la première boucle pas de problème.

Mais là:
Code:

1 2 3 4 5 6 for (int i = 0; i < tab.length; i++) { if(sum-tab[i]<subTT){ return tab[i]; } }
Tu retourne uniquement l'élément du tableau qui permettrait d'atteindre ça. Mais s'il faut en retirer plusieurs, ça marchera jamais.

Déjà, avant de rentrer dans la boucle, il serait bien de vérifier que les conditions sont pas déjà valide. (Sum<subTT) -Ou passer par un while-

Ensuite, comme tu veux en retirer un minimum est que ton tableau est trier, il faut commencer par les plus gros chiffre donc par la fin.
Donc tu commence par la fin, et tu boucle:
La somme du tableau - le dernier élément. Tu vire le dernier élément et tu sauvegarde la nouvelle somme. Et tu regarde si les conditions sont bonnes. (Si oui, hop t'as fini. Si non, tu reboucle.)

PS: je me suis basé sur ton idée, moi je partirais en regardant l'écart subTT/sum. Et après je ferais une somme en commençant par la fin.

EDIT: J'avais pas vu ton deuxième message, surement écrit pendant que j'écrivais le mien. J'ai pas le temps de regarder mais ça me semble complexe. (double boucle imbriquée, etc, ...)
Enfin, si ça marche, tant mieux.
24/07/2012, 09h06
deathness

Citation:

Envoyé par Kearz

EDIT: J'avais pas vu ton deuxième message, surement écrit pendant que j'écrivais le mien. J'ai pas le temps de regarder mais ça me semble complexe. (double boucle imbriquée, etc, ...)
Enfin, si ça marche, tant mieux.

ça me semble aussi inutilement complexe mais bon a lui de voir ce qui lui faut.