Petit problème matriciale

[flex_fan]

Bonjour à tous,

dans le cadre d'un projet, j'aimerais résoudre un problème trés simple (apparement) qui est le suivant:
J'ai un nombre finit N d'objets (N pair), soit O1, O2, ...ON, chacun de ces objets pouvant avoir une ou deux ou M propriétés différentes, P1, P2, ... PM.
Comment peut je séparer N/2 objets parmis les N disponibles, de telle manière que la somme des propriétés des objets selectionnés soit exactement la moitie des propriètés disponibles?

Example: soit O1, O2, O3, O4, O5 et O6 six objets, de telle manière que :
O1 ait les propriétés P1 et P2,
O2 ait les propriètés P1 et P3,
O3 ait les propriètés P2 et P3,
O4 ait les propriètés P1 et P2,
O5 ait les propriètés P1, P2 et P3,
O6 ait les propriètés P2, P2 et P3,

Dans ce cas, la matrice d'apartenance des propriètés aux objets est la suivante:

1 1 0 1 1 0
1 0 1 1 1 2
0 1 1 0 1 1

dans ce cas, on voit bien par example, que dans la première colonne, correspondant à l'objet O1, seulement les P1 (ligne 1) et P2 (ligne 2) sont disponibles.
Le problème à résoudre est donc celui de selectionner parmi les six collones, trois colonnes de telle manière que la somme des propriètés ainsi selectionnées soit la moitie du nombre total de propriètés disponibles.
Dans l'exemple donné, en selectionnant les colonnes (objets) O2, O4 et O6 , la somme des propriètés de ces trois objets est:

2
3
2

ce qui répresente la moitie de toutes les propriètés disponibles.

Commentaire: Biensur qu'il est possible de chercher toutes les combinaisons possible de 3 objets de type O1 et O2 et O3, O1 et O2 et O4, etc, de calculer la sommes des colonnes correspondantes, et de trouver ainsi une solution.
Par contre il y a t'il un moyen de trouver une solution à l'examen seulement des lignes de la matrice d'apartenance ?

Toute ssugestion sera bienvenue.

:help:

[fatal_error]

salut,

une idée comme ca.
On fait la asomme des coeff pour chaque colonne.
Ensuite, l'idée c'est de faire une balance avec ces nous coeff.
Mettons qu'on ait resp
10 8 2 3 4 5
l'idée, c'est d'abord de trier
10 8 5 4 3 2
puis ensuite, d'essayer dequilibrer.
Ici, on a
10|8+2
il reste 5,4,3
10+5|8+2+4+3
et ici, on a pas de solution.

mais j'ai pas la demonstration que ca suffit pour montrer que ya pas de solution si on a pas l'égalité

edit : bon en fait ca marche bien quand on a des nombres gentils. Avec du 5 2 2 2 1 1 ca devient caca.

[flex_fan]

Bonjour,

je t'en remercie pour ta sugestion.

:zen: