J233r244meDelodder
November 27, 2023
113 views
0 votes
2 Answers

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

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.

class ChangeCollection
{
    public function __construct(protected array $denominations = [])
    {
    }

    public function getTotal()
    {
        return array_sum($this->denominations);
    }

    public function getDenominationsString()
    {
        sort($this->denominations);
        return implode(' ', $this->denominations);
    }

    public function addDenominations(array $denominations): array
    {
        return array_map(
            fn (int $denomination) => new ChangeCollection([...$this->denominations, $denomination]),
            $denominations
        );
    }
}

Now, we define a class that actually builds combinations of ChangeCollection objects and checks if it contains the actual solution.

class ChangeCalculator
{
    protected const DENOMINATIONS = [2, 5, 10];

    public function calculate(int $target): ChangeCollection
    {
        $collections = [new ChangeCollection];
        do {
            $collections = array_filter(array_merge(...array_map(
                fn (ChangeCollection $collection) => $collection->addDenominations(self::DENOMINATIONS),
                $collections
            )), fn (ChangeCollection $collection) => $collection->getTotal() <= $target);

            foreach ($collections as $collection) {
                if ($collection->getTotal() === $target) {
                    return $collection;
                }
            }
        } while (count($collections) > 0);

        throw new Exception("There is no possible combination of denominations.");
    }
}

You can now get the string with the outcome with following code:

$calculator = new ChangeCalculator;
echo $calculator->calculate(23)->getDenominationsString();

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:

function addBills(&$change, $value, $count)
{
    $change = array_merge($change, array_fill(0, $count, $value));
}

function removeBill(&$change, $value)
{
    $key = array_search($value, $change);
    if ($key !== false) {
        unset($change[$key]);
    }
}

function getChangeTotal($change)
{
    return array_sum($change);
}

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:

function findMinimum($bills, $wantedTotal, $change = [])
{
    // without bills there's nothing to do
    if (count($bills) == 0) {
        return $change;
    }    
    // get the next smaller bill 
    $value = array_pop($bills);
    // how many of those will fit?
    $count = intdiv($wantedTotal - getChangeTotal($change), $value);
    if ($count > 0) {
        // add as many bills as will fit
        addBills($change, $value, $count);
        while ($count > 0) { 
            // can we find more change?
            $change = findMinimum($bills, $wantedTotal, $change);
            // did we reach the wanted total?
            if ($wantedTotal == getChangeTotal($change)) {
                return $change;
            } else {    
                // we have to use smaller bills
                $count--;
                removeBill($change, $value);
            }    
        }                                  
    }
    // try a smaller bill
    return findMinimum($bills, $wantedTotal, $change);
}

$bills = [2, 5, 10];

print_r(findMinimum($bills, 23));

This is a recursive function. The comments try to explain what it does. The result is:

Array
(
    [0] => 10
    [1] => 5
    [2] => 2
    [3] => 2
    [4] => 2
    [5] => 2
)

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

Please signup or login to give your own answer.

Click here to cancel reply.

Php – Give change using optimal denominations

Rule :

test

problem

Answers