Somme d'entiers - Page 1

En tentant de résoudre un problème d'un concours d'informatique ( www.soinf.ch ), je suis arrivé au problème général suivant :

Soit A = {a1; a2; a3; a4; ... } un ensemble de nombres entiers.
Soit B = {b1; b2; b3; b4; ... } un sous-ensemble de A.

Somme(B) = 1/2 Somme(A)
(b1 + b2 + b3 ...) = 1/2 (a1 + a2 + a3 ...)

Question : si A est connu, comment trouver un sous-ensemble B qui réponde à ce critère ?

La méthode de force brute étant trop lente :-( (compter quelques millénaires)...

Sinon, est-ce que quelqu'un saurait où je peux trouver des indices pour résoudre ce genre de problème ? (J'ai fouillé pendant un après-midi les livres d'algorithmique d'une librairie spécialisée sans résultats...)

mais si ton ensemble A est définit comme ça : A={2 ; 3 ; 8};
Tu ne peux pas définir d'ensmble B, sous ensemble de A, dont la somme des éléments fasse la moitié de la somme des éléments de A.
J'ai peut-être pas bien compris l'énoncé.

non, je ne pense pas ????

jackiechan91 : il est clair que si A={2;3;8} tu ne pourras pas trouver de sous-ensemble dont la somme vale 13/2=6,5. Mais l'idée est de trouver ce sous-ensemble, si il existe, bien entendu.

Par exemple A = {2; 4; 5; 1}

A ce moment-là, la solution est B = {2; 4} ou B = {5; 1}...

La question est : comment trouver un tel sous-ensemble quand le nombre d'éléments de A est grand ?

Ah ok donc il faut trouver B tel que sum(B)=sum(A)/2, et les éléments de B proviennent de A ?

C facile :

Tu fais SortD A, pour trier A par ordre décroissant, puis ensuite tu ajoute à une valeur, disons C, ses éléments un par un. Si C<sum(A)/2, tu continue, si C>sum(A)/2 alors tu enleve le dernier element et tu essaie le suivant dans A (qui sera plus petit).

Et maintenant l'algo en ti-basic

0->c
{}->b
sortd a
for t,1,dim(a)
if c+a[t]<sum(a)/2 then
c+a[t]->c
a[t]->b[dim(b)+1]
elseif c+a[t]=sum(a)/2 then
goto fini
endif
endfor
clrio
pause "Sous ensemble non trouvé"
goto fin
lbl fini
disp "Sous ensemble :"
pause b
goto fin
lbl fin

Ou alors j'ai rien comprit au problème

Edit : je sais pas si ça marche, j'ai pas envie d'essayer. Remarquez au passage : 4 minutes pour écrire ça
[edit]Edité par Bob 64 le 06-03-2002 à 14:54:27[/edit]

Bob == oulaaa ... y'a un petit problème en effet ...

tu utilises des variables a , c , t, mais non !!!! il fallait prendre qq chose de bcp + chiant !!!!

a == l_lte_ent
c == x_var_epx_tmp
t == x_var_f_mov

Pareil pour les labels !!!! Pourquoi un label "fin" alors que tu pouvais mettre lb_n_eprg ???


Ca te ressemblait pas trop tout ça ... corrige toi vite !!!!!

le côté "porcin" de bob aurait-il disparu ?

> Pim89 :
Les noms de variables sont limités à 8 caractères en TI-Basic

J'ai essayé de m'adapter pr être comprit par des newbies comme toi

Bon j'ai résolu le probleme oui ou non ?

j'en ai aucune idée

si je crois que ca marche... Mas ca les trouve pas tous !

mouais, de ttes façon le basic ...

Quessta contre le basic ?

C'est clair que l'algo marche, mais il est bien limité.
Cela dit, je n'ai pas d'idée pour en trouver un mieux

Il a pas dit qu'il fallait trouver toutes les solutions, mais une seule solution

ben justement, ton algo ne trouveras pas toujours la solution, s'il en existe une...

Ah ouais merde...
Il faut qu'il ait un backmachin je sais plus le nom... Enfin c pas bien compliqué à ajouter

ça fonctionne comment un backmachin ?

Bah ça consiste à revenir en arrière quand ça marche pas, en gros
Dans mon algo, il faudrait que si il y arrive pas il vire les 2 derniers éléments puis il en saute un, rééssaie, si ça marche tjrs pas il en vire 3, rééssaie, etc... Jusqu'a ce qu'il arrive au début de la liste. Et si il se retrouve au début de la liste alors ça ne marche pas.

ok

Ah avant de retourner au sujet, juste qques petites choses :

il fallait prendre qq chose de bcp + chiant !!!!
a == l_lte_ent
Pourquoi un label "fin" alors que tu pouvais mettre lb_n_eprg ???
> Tu parle en C ? '=='
> Je déteste programmer avec des variables comme 'a', 'b', 'fin', 'début', etc...

le côté "porcin" de bob aurait-il disparu ?
> C'est pas moi qui peut juger, mais mes codes me semblent pas trop mal optimisés. Mis a part mes noms de variables que vous ne comprenez pas, c'est quoi qui vous fait penser que je code comme un barbare ?
[edit]Edité par Bob 64 le 06-03-2002 à 19:07:21[/edit]

des vars comme a, et b, je trouve que c po évocateur...
mais début et fin, ça l'est assez !

nan, nan, nan.

je met toujours un def_init au début et un def_quit à la fin. Mais bon tu va voir ils vont trouver ça "porcin"

je met jamais de labels, c contraire à l'esprit du C (sauf si c vraiment nécessaire, ce qui est rare) qd je coe... j'en utilises en optimisant

ça ralenti un prog, ou simplement ça donne un aspect bordelique ?

les labels et goto ne ralentissent pas (en C), puisque c'es ce que font les boucles

a=10;
while(a!=0)
{
a--;
}

équivaut me semble-t-il, à ceci :
a=10;
label_debut_boucle:
if(a!=0)
{
a--;
goto label debut_boucle;
}

(il me semble)
toujours est-il que le code ASM généré qd tu utilises des gotos ou des boucles est EXACTEMENT le même.
cela dit, les labels, c bordélique pr comprendre !

nan moi j'adore ça

et puisque ça ralenti pas je sens que je vais pas m'en priver