PostgreSQL La base de donnees la plus sophistiquee au monde.

Forums PostgreSQL.fr

Le forum officiel de la communauté francophone de PostgreSQL

Vous n'êtes pas identifié(e).

#1 02/01/2017 17:01:21

guil31
Membre

Création de sous ensembles dont la somme des valeurs est limitée

Bonjour,


J'ai une table contenant 3 champs:
- id:               identifiant unique de l'objet
- ensemble:    identifiant marquant l'appartenance de l'objet à un ensemble
- valeur:         valeur pour chaque objet


Par exemple:

id        ensemble       valeur
1         1                   5
2         1                   2
3         1                   1
4         2                   4
5         2                   3
6         3                   3
7         4                   1
8         4                   1
9         4                   4
10       4                   2
11       4                   2

Code correspondant:

create table ma_table (id integer, ensemble integer, valeur integer);
insert into ma_table values (1,1,5), (2,1,2), (3,1,1), (4,2,4), (5,2,3), (6,3,3), (7,4 ,1), (8,4 ,1), (9,4 ,4), (10,4 ,2), (11,4 ,2)

Je souhaite faire des sous ensembles à l'intérieur de mes ensembles pour lesquels la somme des valeurs n'excède jamais 6.

id        ensemble       valeur     sous_ensemble   sum_valeur
1         1                   5            1                       6
2         1                   2            2                       3
3         1                   1            1                       6
4         2                   4            1                       4
5         2                   3            2                       3
6         3                   3            1                       3
7         4                   1            1                       4
8         4                   1            1                       4
9         4                   4            2                       6
10       4                   2            2                       6
11       4                   2            1                       4

Ceci en créant de préférence des groupes dont la somme des valeurs est le plus proche possible de 6
et en générant le moins de sous ensemble possible


J'exécute mes requêtes sql depuis un code python 2.7 et je dispose de postgresql 9.1


Comment vous y prendriez-vous?
Merci pour votre aide

Hors ligne

#2 02/01/2017 18:39:54

gleu
Administrateur

Re : Création de sous ensembles dont la somme des valeurs est limitée

J'ai du mal à croire qu'il soit possible d'écrire une requête SQL capable de vous donner ce résultat. Il vous faudra du code procédural, soit dans l'application, soit dans une procédure stockée.


Guillaume.

Hors ligne

#3 02/01/2017 19:04:44

guil31
Membre

Re : Création de sous ensembles dont la somme des valeurs est limitée

Oui c'est bien ce que je pense
mais au niveau des grandes lignes de l'algo, je ne vois pas trop .....

Hors ligne

#4 02/01/2017 20:08:14

rjuju
Administrateur

Re : Création de sous ensembles dont la somme des valeurs est limitée

Il s'agit je pense d'un problème NP-complet, donc soit vous avez suffisamment peu de valeurs pour tester toutes les combinaisons sans faire exploser le temps de calcul, soit vous utilisez des heuristiques pour trouver une approximation suffisante pour vos besoins.

Hors ligne

#5 03/01/2017 13:27:32

guil31
Membre

Re : Création de sous ensembles dont la somme des valeurs est limitée

Je m'en suis finalement sorti avec un enchainement de requêtes qui traitent toutes les combinaisons possibles:

6
5+1           (ou 5 si pas d'enregistrement à 1 disponible)
4+2           
4+1+1       (ou 4+1 ou 4)
3+3           
3+2+1       (ou 3+2)
3+1+1+1   (ou 3+1+1 ou 3+1 ou 3)
....


C'est un peu barbare mais ca marche !

Hors ligne

Pied de page des forums