I’m struggling to solve a problem regarding a script:
Rule :
The cash register only has $2, $5, and $10 bills. Your algorithm should determine the best way to give change for any amount, using the fewest bills possible.
test
Your solution should include tests (unit or otherwise) covering the scenarios provided in the examples, as well as for the specific amounts of 10, 11, 21, 23, and 31 €.
function rendreMonnaie(int $montant)
{
//Déclaration des variables
$listeBillets = [10, 5, 2]; //Liste des coupure dispo
$nbEntree = 0; //Combien de fois un chiffre entre dans le montant
$message = [];
$reste = 0;
$result = 0;
for ($ibillet = 0; $ibillet < sizeof($listeBillets); $ibillet++) {
// Calcul du reste de la division du montant par le billet
$reste = $montant % $listeBillets[$ibillet];
if ($reste == 0) {
// Si le reste est 0, le montant est un multiple du billet
// Calcul du nombre de billets nécessaires
$nbEntree = intdiv($montant, $listeBillets[$ibillet]);
// Ajout du nombre de billets et du type de billet au message
array_push($message, "$nbEntree x $listeBillets[$ibillet]");
break;
} else if ($reste >= $listeBillets[2]) {
// Si le reste est supérieur ou égal au plus petit billet
// Calcul du nombre de billets nécessaires
$nbEntree = intdiv($montant, $listeBillets[$ibillet]);
// Ajout du nombre de billets et du type de billet au message
array_push($message, "$nbEntree x $listeBillets[$ibillet]");
// Mise à jour du montant avec le reste
$montant = $reste;
} else {
if ($listeBillets[$ibillet] == 2) {
$nbEntree = intdiv($result, $listeBillets[$ibillet]);
array_push($message, "$nbEntree x $listeBillets[$ibillet]");
} else {
$result = $montant - $listeBillets[$ibillet];
$reste = $reste % $listeBillets[$ibillet];
// Calcul du nombre de billets nécessaires
$nbEntree = intdiv($result, $listeBillets[$ibillet]);
array_push($message, "$nbEntree x $listeBillets[$ibillet]");
}
}
}
// Affichage du tableau message pour le débogag
for ($i = 0; $i < sizeof($message); $i++) {
// Suppression des éléments du message qui commencent par un nombre inférieur à 1
if ($message[$i][0] < 1) {
unset($message[$i]);
}
}
// Conversion du tableau message en une chaîne de caractères
$message = implode(" + ", $message);
echo ($message);
}
problem
I’m struggling to include the solution for numbers like 23, 31
I try to do so :
23%10 = 3
3 + 10 = 13
13%5 = 3
3 + 5 = 8
// output 1 x 10 + 1 x 5 + 4 x 2
2
Answers
I came up with a solution, but it’s by no means optimal (especially when the target amount becomes rather large). First let’s define a class that contains a collection of multiple denominations that might contain a solution to the problem.
Now, we define a class that actually builds combinations of
ChangeCollection
objects and checks if it contains the actual solution.You can now get the string with the outcome with following code:
I kept my solution quite simple. First I started with creating two function that can add and remove bills from a simple array, and one function to sum the bills in that array:
These helper functions come in handy to keep track of what I’m doing in the function that computes the minimal number of bills to return:
This is a recursive function. The comments try to explain what it does. The result is:
I did not create a nice output message, but this shouldn’t be hard to do.
For a live demo see: https://3v4l.org/TCRIA