Vous n'êtes pas identifié(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
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
Oui c'est bien ce que je pense
mais au niveau des grandes lignes de l'algo, je ne vois pas trop .....
Hors ligne
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/
Hors ligne
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