How many different ways can £2 be made using any number of coins

  • 时间：2020-09-10 12:45:51
  • 分类：网络文摘
  • 阅读：148 次

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Depth First Search Algorithm

Let’s define a function f takes two parameters (amount and last). Thus, we can perform a Depth First Search (DFS) search based on the following

tex_a70d0d338299cc17a407f6a31bf41c55 How many different ways can £2 be made using any number of coins? (Depth First Search and Dynamic Programming) algorithms DFS dynamic programming javascript math project euler

The f(0, x) is 1. We avoid duplicate solution by limiting the current coin strictly less or equal than the last coin.

1
2
3
4
5
6
7
8
9
10
11
12
13

function dfs(amount, last) {
    if (amount === 0) return 1;
    const coins = [1, 2, 5, 10, 20, 50, 100, 200];
    let ans = 0;
    for (let x of coins) { // iterate over the coins
        if (amount- x >= 0 && x <= last) { // non-bigger
            ans += dfs(amount - x, x);  // recursive dfs
        }
    }
    return ans;
}
 
console.log(dfs(200, 200));
function dfs(amount, last) {
    if (amount === 0) return 1;
    const coins = [1, 2, 5, 10, 20, 50, 100, 200];
    let ans = 0;
    for (let x of coins) { // iterate over the coins
        if (amount- x >= 0 && x <= last) { // non-bigger
            ans += dfs(amount - x, x);  // recursive dfs
        }
    }
    return ans;
}

console.log(dfs(200, 200));

The answer is 73682. We can also place a non-less coin and we need to call initially with last equal to 0:

1
2
3
4
5
6
7
8
9
10
11
12
13

function dfs(amount, last) {
    if (amount === 0) return 1;
    const coins = [1, 2, 5, 10, 20, 50, 100, 200];
    let ans = 0;
    for (let x of coins) { // iterate over the coins
        if (amount- x >= 0 && x >= last) { // non-smaller
            ans += dfs(amount - x, x); // recursive dfs
        }
    }
    return ans;
}
 
console.log(dfs(200, 0));
function dfs(amount, last) {
    if (amount === 0) return 1;
    const coins = [1, 2, 5, 10, 20, 50, 100, 200];
    let ans = 0;
    for (let x of coins) { // iterate over the coins
        if (amount- x >= 0 && x >= last) { // non-smaller
            ans += dfs(amount - x, x); // recursive dfs
        }
    }
    return ans;
}

console.log(dfs(200, 0));

Counting Number of Coins using Dynamic Programming Algorithm

We notice that we can save the intermediate results so that we don’t respawn too many recursions. The easiest way is to pass a dictionary (or hash map) as a last parameter.

The following Javascript code implements the Dynamic Programming Algorithm to count the coins based on the Recursive Depth First Search with Memoization Technique.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function dfs(amount, last, cached = {}) {
    if (amount === 0) return 1;
    const coins = [1, 2, 5, 10, 20, 50, 100, 200];
    // if it has been calculated, then return it
    if (typeof cached[amount + "-" + last] !== "undefined") {
        return cached[amount+ "-" + last];
    }
    let ans = 0;
    for (let x of coins) {
        if (amount - x >= 0 && x >= last) {
            ans += dfs(amount- x, x, cached);
        }
    }
    // save the result in the memo
    cached[amount+ "-" + last] = ans;
    return ans;
}
 
console.log(dfs(200, 0));
function dfs(amount, last, cached = {}) {
    if (amount === 0) return 1;
    const coins = [1, 2, 5, 10, 20, 50, 100, 200];
    // if it has been calculated, then return it
    if (typeof cached[amount + "-" + last] !== "undefined") {
        return cached[amount+ "-" + last];
    }
    let ans = 0;
    for (let x of coins) {
        if (amount - x >= 0 && x >= last) {
            ans += dfs(amount- x, x, cached);
        }
    }
    // save the result in the memo
    cached[amount+ "-" + last] = ans;
    return ans;
}

console.log(dfs(200, 0));

We can slightly rewrite this, using iterative approach. We sort the coins and start from the smallest coin. For each coin, we then incrementally update the answer.

1
2
3
4
5
6
7
8
9
10

function dp(amount) {
    let f = Array(amount + 1).fill(0);
    f[0] = 1;
    for (let x of [1, 2, 5, 10, 20, 50, 100, 200]) {
        for (let a = x; a <= amount; ++ a) {
            f[a] += f[a - x];
        }
    }
    return f[amount];
}
function dp(amount) {
    let f = Array(amount + 1).fill(0);
    f[0] = 1;
    for (let x of [1, 2, 5, 10, 20, 50, 100, 200]) {
        for (let a = x; a <= amount; ++ a) {
            f[a] += f[a - x];
        }
    }
    return f[amount];
}

The algorithmic complexity is O(NM) where N is the number of the coin-types and M is the amount. The space complexity is O(M).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
臧僖伯谏观鱼原文及翻译　 石碏谏宠州吁原文及翻译　 周郑交质原文及翻译　 郑伯克段于鄢原文及翻译　 曲谱列表　 奥数题:A+B=2300，小红计算时将A个位上的0漏掉了　 数学题:甲乙二人同时从A地出发匀速走向B地　 数学题:一种农药用药液和水按照1:1500配制而成　 数学题:回收1千克废纸，可生产0.8千克再生纸　 数学题:丢番图的墓志铭　
评论列表
添加评论