最少硬币找零问题的动态规划解与贪心算法解

算法
Catalogue
  1. 1. 基于动态规划的算法
  2. 2. 基于贪心算法思路的最少找零硬币解
  3. 3. 性能分析与求解对比

最少硬币问题找零问题是说，已知某种硬币系统 [Ci, …]，以及期望凑齐的找零值 Amount，找到硬币数量最少的那个找零方案：

∑NiCi = Amount 且 ∑Ni 最小

基于动态规划的算法

动态规划（Dynamic Programming，DP）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 基于动态规划的算法
 * @param {Array} coins [description]
 */
module.exports = function MinCoinChange(coins) {
  var coins = coins || [];
  var cache = {};

  this.makeChange = (amount) => {
    if (amount < 1) {
      return [];
    }

    if (cache[amount]) {
      return cache[amount];
    }

    var min = [];
    var newMin;
    var newAmount;

    for (var i = 0; i < coins.length; i++) {
      var coin = coins[i];
      newAmount = amount - coin;

      if (newAmount >= 0) {
        newMin = this.makeChange(newAmount);
      }

      if (newAmount >= 0 &&
        (newMin.length < min.length - 1 || !min.length) &&
        (newMin.length || !newAmount)
      ) {
        min = [coin].concat(newMin);
      }
    }

    return (cache[amount] = min);
  };

  this.getCache = function() {
    return cache;
  };
}

基于贪心算法思路的最少找零硬币解

贪心算法会试图通过每个阶段的最优解，来找到全局的最优解。这是一种近似解决问题的技术。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 基于贪心算法思路的最少找零硬币解
 * @param  {Array} coins [description]
 */
module.exports = function MinCoinChange(coins) {
  var coins = coins || [];

  this.makeChange = (amout) => {
    var change = [];
    var total = 0;
    for (var i = coins.length - 1; i >= 0; i--) {
      var coin = coins[i];
      while(total + coin <= amout) {
        change.push(coin);
        total += coin;
      }
    }

    return change;
  };
}

性能分析与求解对比

性能分析代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var MinCoinChange1 = require('./coins-1.js');
var MinCoinChange2 = require('./coins-2.js');

var arr = [1, 3, 4];
var NUM = 10000;
var AMOUT = 6;

var mcc1 = new MinCoinChange1(arr);
var mcc2 = new MinCoinChange2(arr);


console.time('动态规划');
for (var i = 0; i < NUM; i++) {
  mcc1.makeChange(AMOUT);
}
console.timeEnd('动态规划');


console.time('贪心算法');
for (var i = 0; i < NUM; i++) {
  mcc2.makeChange(AMOUT);
}
console.timeEnd('贪心算法');

执行的结果：

  • 动态规划: 0.843ms
  • 贪心算法: 4.547ms

这可以大概认为，动态规划要比贪心算法合理、快速。

Share