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

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

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

推荐阅读：
诗词名句鉴赏：我思古人，实获我心。　 诗词名句鉴赏：投我以木桃，报之以琼瑶。　 诗词名句鉴赏：知我者，谓我心忧；不知我者，谓我何求。　 齐桓公伐楚盟屈完原文及翻译　 曹刿论战原文及翻译　 数学题:组成只能被3整除不能被9整除的4位数　 数学题:将某款服装按标价打8折出售，仍可盈利10%　 数学题:把一根长30cm，底面半径是8cm的圆木平均锯成4段　 数学题:甲乙两种皮鞋的原价相同，换季时　 奥数题:1994年“世界杯”足球赛中　
评论列表
添加评论