How to calculate voucher denominations for a given number

See more:

Javascript

PHP

Python

algorithm

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:

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:

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