Click here to Skip to main content
15,306,142 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
So I have scoured the internet for this but I haven't found a solution, yet.

The Problem: We have a number of supermarkets in the UK and each of them has its own set of voucher denominations. E.g. Tesco is [100, 75, 50, 25, 10], and ASDA is [100, 50, 25, 20, 10, 5].

I need a function that takes the total amount and returns an array of various denominations that make up that amount. For example:

JavaScript
let amount = 80;
getDenominations(amount);
// this should return 50 x 1, 10 x 3 for Tesco
// and 50 x 1, 25 x 1, 5 x 1 for Asda

There are plenty of algorithms out there for calculating change with 'greedy' approach, but none of them work primarily because the last denomination for each supermarketing is anything but 1. Greedy approach works fine only when the last denomination is one, so it can easily assign 1s to the remainder.

What I have tried:

I have tried a number of methods that seem to work most of the time, but on occasions, they fail.

Of course, I understand there will be some numbers e.g. 23 that will always have a remainder, and I am fine with that. I am only after numbers that logically can be divided up without leaving a remainder.

For example, with the work I've done so far, I can quite successfully process 10, 20, 30, 35, 40, 45, 50... with Tesco vouchers. But with 55 it fails, and the reason for that is:

It comes across 25, times that by 2, to get 50, and then fails to find a denomination for the remaining 5. The other way around, it finds 10, times that by 5 to get 50, but is left with a 5 and no denomination for it. Ideally, it should simply get one of 25 and 3 of 10 to get 55.

Any ideas how to solve this problem?

Here is one variation of my numerous attempts:

JavaScript
function calculateVouchersDenominations(amount, voucher) {

    var vouchers = {
        'asda': [100, 50, 25, 20, 10, 5],
        'tesco': [100, 75, 50, 25, 10],
        'sainsburys': [100, 50, 25, 10],
        'morrisons': [45, 30, 25, 15, 10, 5],
        'one4all': [45, 30, 25, 15, 10, 5],
        'primark': [200, 190, 180, 170, 160, 150, 140, 130, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 5],
        'iceland': [200, 100, 50, 10]
    }

    var denominations = vouchers[voucher];

    if (denominations === undefined)
        return [];

    var voucherCounter = [];
    denominations.forEach(function (row, i) {
        voucherCounter[i] = 0;
    });

    // count denominations using
    // Greedy approach
    for (i = 0; i < denominations.length; i++)
    {
        if (amount >= denominations[i])
        {
            voucherCounter[i] = parseInt(amount / denominations[i]);
            amount = amount - voucherCounter[i] * denominations[i];
        }
    }

    var out = [];
    for (i = 0; i < denominations.length; i++)
    {
        if (voucherCounter[i] !== 0)
        {
            out[denominations[i]] = voucherCounter[i];
        }
    }

    return out;
}
Posted
Updated 2-Aug-21 14:37pm
v2
Comments
Patrice T 2-Aug-21 14:36pm
   
Show your code so we see why you failed.
Saleem Beg 2-Aug-21 15:09pm
   
Here is one variation of my numerous attempts:

function calculateVouchersDenominations(amount, voucher) {

var vouchers = {
'asda': [100, 50, 25, 20, 10, 5],
'tesco': [100, 75, 50, 25, 10],
'sainsburys': [100, 50, 25, 10],
'morrisons': [45, 30, 25, 15, 10, 5],
'one4all': [45, 30, 25, 15, 10, 5],
'primark': [200, 190, 180, 170, 160, 150, 140, 130, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 5],
'iceland': [200, 100, 50, 10]
}

var denominations = vouchers[voucher];

if (denominations === undefined)
return [];

var voucherCounter = [];
denominations.forEach(function (row, i) {
voucherCounter[i] = 0;
});

// count denominations using
// Greedy approach
for (i = 0; i < denominations.length; i++)
{
if (amount >= denominations[i])
{
voucherCounter[i] = parseInt(amount / denominations[i]);
amount = amount - voucherCounter[i] * denominations[i];
}
}

var out = [];
for (i = 0; i < denominations.length; i++)
{
if (voucherCounter[i] !== 0)
{
out[denominations[i]] = voucherCounter[i];
}
}

return out;
}
Patrice T 2-Aug-21 15:20pm
   
updated your question.
Saleem Beg 2-Aug-21 15:24pm
   
Thanks!
Patrice T 2-Aug-21 16:07pm
   
"I need a function that takes the total amount and returns an array of various denominations that make up that amount."
Are you looking for 1 solution per supermarket or all possible solutions per supermarket ?
Saleem Beg 2-Aug-21 17:33pm
   
Ideally, it should be one function that intelligently works out the sum for different combinations, so potentially one can throw any supermarket (or anything else for that matter) and it should work.

Another variation I tried was to create a powerset of all the vouchers. So it creates combinations of all the different denominations and processes them through the above function. It is probably the most accurate solution I have found so far, but even then in some cases, it fails. E.g. with number 55 it should look at the subset [25,10] and return 25 x 1 and 10 x 3. But it deals with 25 first (rightly so) but times it by 2 to get 50, and then cannot find any denomination for the remaining 5. If I were to reverse the subset (10, 25), it would times 10 by 5 to get 50, but again, be left with 5.

1 solution

Quote:
I have tried a number of methods that seem to work most of the time, but on occasions, they fail.

Never heard of backtracking algorithm and recursion algorithm ?
Backtracking - Wikipedia[^]
Recursion (computer science) - Wikipedia[^]
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900