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

最少硬币问题找零问题是说,已知某种硬币系统 [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