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[^]

See more:

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:

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:

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

Copy Code

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.

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

Copy Code

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; }

Comments

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 - 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

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;

}

Are you looking for 1 solution per supermarket or all possible solutions per supermarket ?

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.