Forums PostgreSQL.fr

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

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.

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 .....

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.

---

Julien.
https://rjuju.github.io/

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 !