Problème de courses en python (facile pour vous, difficile p

[thomas34]

Bonjour à tous,

J'ai un problème assez particulier, que je vais essayer de décrire en espérant être compris.
D'après une liste de courses (avec prix), je souhaiterais un algorithme qui puisse regrouper les prix par groupe avec le moins de perte possible.

Un exemple pour être plus clair :

Groupe de 5 euros.
1. Riz : 2.30
2. Pates : 1.20
3. Lentilles : 3.00
4. Tomates: 2.40
5. Coca: 1.50

La sortie de l'algorithme me donnerait :

#1 : Riz; Pates; Coca : 5 euros
#2 : Lentilles ; Tomates : 5.40 euros (40ct de depassement)

J'ai essayé de faire une boucle qui continue à l'index + 1 si la somme est supérieure au groupe donné, mais ca finit toujours en boucle infinie..
Et je suppose qu'il doit y avoir un calcul, théorème, algo déjà appliqué an mathématiques ou algorithme sans devoir tout réapprendre.

Sachant que cette liste peut aller jusqu'à 100 entrées voir plus et que le dernier groupe ne dois pas non plus être trop inférieur genre deux euros et pas trop supérieur d'un euro également.

En vous remerciant pour vos réponse.

[lyceen95]

Dans un premier temps, il faut que tu définisses des règles précises.
Par exemple, tu as une 'solution' qui te donne (5€+5€50+5€50) et une autre qui te donne (5€ + 5€+ 6€) , tu préfères quelle solution.
J'ai pris cet exemple, mais il faut que tu définisses une règle générale.
' pas trop inférieur', ce n'est pas assez précis, çe ne peut pas se traduire en langage informatique.

Il y a un 2ème problème, c'est que 100 entrées, c'est beaucoup. En programmant comme un bourrin, le programme va devoir explorer 100000000000000000000000000000000000000000000000000000 solutions.
Là, il y a des principes qui vont te permettre d'avancer un peu.

Si tu as 2 articles dont la somme donne 5€, tu associes ces 2 articles. Et tu passes de 100 à 98 articles.
Avec des groupes de 2 articles, tu peux le faire, pas de problème.
Par contre, avec des groupes de 3 articles, ce n'est pas forcément bon.
Par exemple , tu as 8 articles 2.2, 2.3, 2.4, 0.5, 0.4 , 3, 1.5
Si tu associes (2.2, 2.3, 0.5) il te reste (2.4, 0.4, 3, 1.5) et tu ne peux plus faire de groupe qui donne 5€
Alors que si tu associes (2.2, 2.4, 0.4), avec les articles restants, tu peux encore faire (3, 1.5, 0.5)

Le traitement est donc une succession de tests, et de retours en arrière. C'est difficile à programmer.

Il y a peut-être des 'bibliothèques' Python qui font ça quasi automatiquement, mais tu auras plus de réponses sur un forum dédié à Python.

[fatal_error]

Hi

Une approche tres simple
Tu génères ts les groupes de taille 1 que j'appelle F1.
Pour chaque groupe de F1, tu génères ts les groupes de taille 2.
Tu continues jusqu'à ce que Fk soit vide
Pdt les generations tu ignores tout groupe dont la somme depasse ton max

[fatal_error]

ex en js:
https://jsfiddle.net/71vns8cu/

Code: Tout sélectionner

const elems = { riz: 2.3, patate: 1.2, lentille: 3, tomate: 2.4, coca: 1.5 }
const A = Object.entries(elems).map(([k, v]) => ({ k, v })).sort((a, b) => a.v - b.v)
//const A = '0'.repeat(50).split('').map((x, i) => ({ k: `k${i}`, v: 1 + Math.random() }))
const MAX = 5.4
const MIN = 4.6


// i: index of the last element added to the group
// s: group sum
const g0 = [{ i: -1, s:0 }]
const gs = [g0]
while (gs.at(-1).length && gs.at(-1).length < 3e6) {
  const gn = gs.at(-1)
  const gnp = []
  gn.forEach(group => {

    for (let i = group.i + 1; i < A.length; ++i) {
      const s = group.s + A[i].v;
      if (s < MAX) {
        gnp.push({ s, i, el: A[i], from: group })
      }
    }
  })
  gs.push(gnp)
}

const toString = (g, recSymbol) => {
  if (!g || !g.el) return ''
  if (recSymbol) return `${recSymbol} ${g.el.k} (${g.el.v}) ${toString(g.from, '+')}`
  return `${g.s} ${toString(g, '<=')}`
}
const solutions = gs.flatMap(g => g).filter(x => x.s > MIN).sort((a, b) => b.s - a.s)
console.log(solutions.map(g => toString(g)).join('\n'))
/*
5.3 <= lentille (3) + riz (2.3)
5.1 <= tomate (2.4) + coca (1.5) + patate (1.2)
5 <= riz (2.3) + coca (1.5) + patate (1.2)
4.699999999999999 <= tomate (2.4) + riz (2.3)
*/