Discussion :

[JPBruneau]

Bonjour, Pour une grande surface PRO, je traites l'arrivée des chèques de ses gros clients qui flemmards,
envoient souvent un chèque en règlement de une mais souvent trois quatre factures sans les préciser.
Ors il y a des milliers de factures.

Tout le site est en AJAX et les factures chèques etc... sont en MYSQL (PDO)
Ce que je souhaites réaliser se fera en Javascript ,si le module que je cherches à réaliser est faisable

Donc a chaque requête, je reçois
Le montant du chèque,
l'Array des facture
et l'array des montants.

Je dois préciser qu'il y a dans les "factures" des avoirs ce qui complique l'ALGO à réaliser,
J'ais cherché par google mais la question est pas facile à formuler, et je ne suis pas assez pointu pour réaliser ceci moi-même.


Un exemple le client Durand à en impayé les factures

1) 1815.80
2) 899.15
3) 1400.00
4) 789.65
5) 412.18

Son Chèque est de 2100.98

Bon courage et merci d'avance si vous acceptez ce défi ,en me mettant au moins sur une piste..

[NoSmoking]

Bonjour,
cela me fait penser au problème du sac à dos.

Tu peux utiliser la méthode de la force brute, tester toutes les possibilités et arrêter le traitement lorsqu'une occurrence est trouvée.

Plusieurs soucis peuvent quand même se présenter :

• quel est le nombre de factures potentielles à traitées. Le nombre de solutions possibles étant de 2^n, cela peut vite de devenir gourmand :
  
  • 2^10 = 1024, jouable rapidement ;
  • 2^20 = 1048576, là ça pique les yeux.
• plusieurs solutions peuvent répondre à la demande, laquelle est la bonne ;
• une erreur dans le montant ne permet pas d'avoir de solution exacte
• ... et sûrement d'autres

Donc cela est faisable mais pas forcément simplement.

[JPBruneau]

En fait j'ai un CodePen qui me va bien mille mercis
https://codepen.io/jplyne/pen/RwRpWEB

[NoSmoking]

En fait j'ai un CodePen qui me va bien mille mercis

Content pour toi.

L'exercice m'étant apparu comme intéressant je te livre ma solution :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const tabDatas = [100, 200, 125, 150, 175, 200, 250];
const search = 550.0;
/**
 * @param {Array|number]}  datas - tableau des données numérique
 * @param {number}         value - valeur de la somme à trouver
 * @return {object} Array des données trouvées
 */
function searchOccurrence(datas, ref) {
  // on travaille sur des valeurs entières
  // pour éviter les soucis d'arrondi
  const MULTI = 100;
  datas = datas.map((val) => val * MULTI);
  ref = ref * MULTI;
 
  const nbr = datas.length;
  const ret = [];
  const nbrCas = 1 << nbr;                // 2^n cas possibles soit au total (2^n)*n traitements
 
  // pour toutes les combinaisons possibles
  for (let i = 0; i < nbrCas; i += 1) {
    // récupération de la combinaison
    // ex : ["0", "1", "0", "1", "0"] pour la valeur 10
    //      ["1", "1", "1", "0", "0"] pour la valeur 28
    const etats = i.toString(2).padStart(nbr, "0").split("");
    const values = [];
    let somme = 0;
    // on traite chaque cas
    etats.forEach((etat, ind) => {
      if (etat * 1) {
        const val = (+etat * datas[ind]);
        somme += val;
        values[values.length] = val;
      }
    });
    // store les infos
    if( somme == ref){
      ret[ret.length] = {
        "values" : values.map((val) => (val / MULTI).toFixed(2)),
        "somme": (somme / MULTI).toFixed(2)
      };
    }
  }
  // tri croissant suivant somme ça peut servir
  ret.sort((a, b) => a.somme - b.somme);
  return ret;
}
 
function writeResult(datas) {
  const ret = ["Solution(s) :"];
  datas.forEach((data) => {
    ret[ret.length] = data.values.join(" + ") + " = " + data.somme;
  })
  console.log(ret.join("\n"));
}
 
writeResult(searchOccurrence(tabDatas, search));

Je n'ai regardé ta solution que rapidement et elle semble faire le job, dans la mienne je retourne toutes les possibilités et donc pourrait être interrompue à la première occurrence trouvée.

Nota : attention quand même aux réserves levées dans mon précédent post.

[JPBruneau]

C'est un peut la honte, je n'arrives pas à intégrer ta solution dans un simple HTML !
Peux tu me dire ou je me plantes, merci d'avance

Code HTML :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
<html lang="fr">
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
</head>
<body>
<h1>Liste des éléments d'un tableau dont la somme est un nombre donné</h1><br />
<script>
const tabDatas = [100, 200, 125, 150, 175, 200, 250];
const search = 550.0;
/**
 * @param {Array|number]}  datas - tableau des données numérique
 * @param {number}         value - valeur de la somme à trouver
 * @return {object} Array des données trouvées
 */
function searchOccurrence(datas, ref) {
  // on travaille sur des valeurs entières
  // pour éviter les soucis d'arrondi
  const MULTI = 100;
  datas = datas.map((val) => val * MULTI);
  ref = ref * MULTI;
 
  const nbr = datas.length;
  const ret = [];
  const nbrCas = 1 << nbr;                // 2^n cas possibles soit au total (2^n)*n traitements
 
  // pour toutes les combinaisons possibles
  for (let i = 0; i < nbrCas; i += 1) {
    // récupération de la combinaison
    // ex : ["0", "1", "0", "1", "0"] pour la valeur 10
    //      ["1", "1", "1", "0", "0"] pour la valeur 28
    const etats = i.toString(2).padStart(nbr, "0").split("");
    const values = [];
    let somme = 0;
    // on traite chaque cas
    etats.forEach((etat, ind) => {
      if (etat * 1) {
        const val = (+etat * datas[ind]);
        somme += val;
        values[values.length] = val;
      }
    });
    // store les infos
    if( somme == ref){
      ret[ret.length] = {
        "values" : values.map((val) => (val / MULTI).toFixed(2)),
        "somme": (somme / MULTI).toFixed(2)
      };
    }
  }
  // tri croissant suivant somme ça peut servir
  ret.sort((a, b) => a.somme - b.somme);
  return ret;
}
 
function writeResult(datas) {
  const ret = ["Solution(s) :"];
  datas.forEach((data) => {
    ret[ret.length] = data.values.join(" + ") + " = " + data.somme;
  })
  console.log(ret.join("\n"));
}
 
writeResult(searchOccurrence(tabDatas, search));
</script>
 
</body>
</html>

[NoSmoking]

je n'arrives pas à intégrer ta solution dans un simple HTML

j'ai du mal à voir ce que tu n'arrives pas à faire !

Pour avoir une sortie écran, il te suffit d'avoir, par exemple, un élément <pre id="console"></pre> dans ta page et de modifier la fonction writeResult pour rediriger le résultat de la console vers celui-ci.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
function writeResult(datas) {
  const ret = ["Solution(s) :"];
  datas.forEach((data) => {
    ret[ret.length] = data.values.join(" + ") + " = " + data.somme;
  })
  // on supprime
  // console.log(ret.join("\n"));
  // on ajoute
  document.getElementById("console").textContent = ret.join("\n")
}

Au passage je te mets une nouvelle version de la fonction searchOccurrence « optimisée », à peine ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * @param {Array[number]}  datas - tableau des données numérique
 * @param {number}         value - valeur de la somme à trouver
 * @return {object} Array des données trouvées
 * ------------------------------------------------------------
 * inversion des tableaux pour limiter le nombre de cas traités,
 * non prise en compte des zéros non significatif lors de valeur.string(2)
 * on ne traite pas 2^n cas, on a (2^n)*(n-1) traitements
 */
function searchOccurrence(datas, ref) {
  // on travaille sur des valeurs entières
  // pour éviter les soucis d'arrondi
  const MULTI = 100;
  // tri ordre décroissant
  datas.sort((a, b) => b - a);
  datas = datas.map((val) => val * MULTI);
  ref = ref * MULTI;
 
  const nbr = datas.length;
  const ret = [];
  const nbrCas = 1 << nbr;                // 2^n cas possibles soit au total (2^n)*n traitements
 
  // pour toutes les combinaisons possibles
  for (let i = 0; i < nbrCas; i += 1) {
    // récupération de la combinaison
    // ex : ["0", "1", "0", "1", "0"] pour la valeur 10
    //      ["1", "1", "1", "0", "0"] pour la valeur 28
    // inverse le tableau des états
    const etats = i.toString(2).split("").reverse();
    const values = [];
    // on traite chaque cas
    const nbEtats = etats.length;
    let somme = 0;
    for (let ind = 0; ind < nbEtats; ind += 1) {
      count += 1;
      const val = (+etats[ind] * datas[ind]);
      if (val) {
        somme += val;
        if (somme > ref) break;
        values[values.length] = val;
      }
    }
    // store les infos
    if( somme == ref){
      ret[ret.length] = {
        "values" : values.map((val) => (val / MULTI).toFixed(2)),
        "somme": (somme / MULTI).toFixed(2)
      };
      //return ret      // <- si on ne veut qu'une solution
    }
  }
  return ret;         // <- si on veut toutes les solutions
}

[JPBruneau]

Tu es trop sympa mille mercis