Algorithme mathématique pour le calcule du paiement en pièces Fermé

Question

Bonjour !

J'essaie de trouver la réponse la plus simple possible à un calcule mathématique que je doit faire dans un programme informatique.

Partie logique.

Le système simule une caisse d'un magasin dans le quel il y a plein de chèques repas. 
Lorsqu'un fournisseur arrive au magasin le système doit calculer la combinaison de chèques repas à donner pour payer la facture de la façon la plus performante possible.

Il faut que les suivantes conditions soient respectés:

1 - La combinaison de chèques repas doit se faire de façon à éliminer de la caisse les  chèques repas les plus petits.

2 - La combinaison de chèques repas doit être égale au montant ou, si cela n'est pas possible, la combinaison doit être supérieur par le montant le plus bas possible. (si ce n'est pas possible de payer exactement 7.50€ alors il faut qu'il indique la combinaison pour arriver à 7.65€ par exemple)

Partie progra.

Le programme est en PhP mais ce qui m'intéresse n'est pas le code mais la logique des boucles à réalisé (pour cette raison le problème est dans la partie programmation et non pas dans celle PhP). J'ai un array avec ceci:

$cheques = array(
  '12.12' => 0,
  '10.00' => 10,
  '8.00' => 1,
  '7.15' => 12,
  '7.00' => 115,
  '6.60' => 4,
  '6.00' => 38,
  '5.60' => 1
);


EXEMPLE:
°°°°°°°°

Voici une table avec des chèques repas :

Valeur   |   Nombre 
_________________
12.12   0 
10.00 10 
8.00           1 
7.15         12 
7.00       115 
6.60      4 
6.00         38 
5.60        1 



CAS DE FIGURE n° 1 : 
°°°°°°°°°°°°°°°°°°

Il faut payer 7.00€

Le résultat doit indiquer:
1 x 7 = 7.00
Reste : 0.00€ 


CAS DE FIGURE n° 2 : 
°°°°°°°°°°°°°°°°°°

Il faut payer 9.00€

Le résultat doit indiquer:
1 x 10 = 10.00
Reste : 1.00€ 


CAS DE FIGURE n° 3:
°°°°°°°°°°°°°°°°°°

Il faut payer 25€
4 x 6 = 24.00
1 x 5.60 = 5.60
total en chèques : 29.60€
Reste : 4.60€ 
 

 

Merci pour vos réponses !

liquidd666 · Answer

J'ai trouvé ceci pour ceux à qui cela intéresse... je ne sais pas si c'est la meilleur solution au problème dans le cas concret que j'ai présenté mais il semble assez intéressant.

https://openclassrooms.com/fr/courses 
 
--

KX · Answer

Je viens de le faire vite fait en Java, et pour l'exemple 3 il y a un meilleur résultat :

Il faut payer 25€
3 x 6 = 18.00
1 x 7 =  7.00
Total en chèques : 25.00€
Reste : 0.00€
Si tu connais Java voici le code :

import ccm.kx.enumerator.Bounds;
import ccm.kx.enumerator.Enumeration;

public class Test
{
    public static void main(String[] args)
    {
        long[][] val = // Note : il est important que les valeurs à choisir de préférence soient en fin de tableau
        {
                {1212,   0},
                {1000,  10},
                { 800,   1},
                { 715,  12},
                { 700, 115},
                { 660,   4},
                { 600,  38},
                { 560,   1}
        };
        
        rendreMonnaie(val, 700);
        rendreMonnaie(val, 900);
        rendreMonnaie(val, 2500);
    }
    
    public static void rendreMonnaie(long[][] val, long x)
    {
        int n = val.length;
        
        long[] res = null;
        long best = Long.MAX_VALUE;
        
        long[] end = new long[n];
        for (int i = 0; i < n; i++ )
            end[i] = Math.min(val[i][1], x / val[i][0] + 1);
        
        Enumeration e = new Enumeration(n, Bounds.make(0), Bounds.make(end), Bounds.make(1), false);
        
        for (long[] tab : e)
        {
            long sum = 0;
            
            for (int i = 0; i < n; i++ )
                sum += val[i][0] * tab[i];
            
            if (sum >= x && sum - x < best)
            {
                best = sum - x;
                res = tab;
            }
        }
        
        System.out.println("Il faut payer  " + x);
        
        for (int i = 0; i < n; i++ )
            if (res[i] != 0)
                System.out.println(res[i] + " x  " + val[i][0] + " =  " + (res[i] * val[i][0]));
        
        System.out.println("Total en chèques :  " + (x + best));
        System.out.println("Reste : " + best);
        System.out.println("Nombre de combinaisons testées : " + e.getCardinality());
        System.out.println();
    }
}
Sachant que j'utilise ici le package ccm.kx.enumerator

Algorithme mathématique pour le calcule du paiement en pièces

2 réponses

Discussions similaires