阅读 259

快速入门数据结构与算法之贪心、分治与动态规划

前言

上一篇我们学习了一些查找和排序的算法,今天我们来学习几个设计算法时常用的策略。本篇要介绍的策略有

  • 贪心策略
  • 分而治之策略
  • 动态规划策略

很多同学都会觉得对这些策略不太理解?分治和动态规划分不清?下面我们一步一步的真正的去理解他们。

贪心策略

贪心策略是比较好理解的,略是一种近似解决问题的技术,所谓贪心,就是先选择当前阶段的最优解,不去考虑这次的选择会不会对未来造成影响,想要通过每个阶段的局部最优解,达到全局最优解。也就相当于我们去吃自助,胃就那么大,先挑贵的吃,贵的吃不下了再挑次贵的吃,最后就心理安慰能多吃回一点。(其实很少能吃回来)。下面我们用贪心策略来吃(jie)一个经典的题目:最少硬币找零问题

假设你为一家自动售货机厂家编程序,自动售货机要每次找给顾客最少数量硬币,美国有以下面额的硬币:1美分、5美分、10美分、25美分。比如说要找36美分的零钱,我们可以用1个25美分、1个10美分和一个1美分

贪心算法的思想就是从最大面值的硬币开始,用尽量多的硬币,如果有余额,就用下一个最大面值的尽量多的硬币,一直到最小面值为止。下面我们用JavaScript代码来实现一下

function minCoinChange(amount, coins) {
	let minCoin = amount,
		count = 0;
	for (let i = coins.length; i >= 0; i--) { // 从大到小迭代硬币面额
		if (coins[i] <= minCoin) {
			count += Math.floor(minCoin / coins[i]); // 此面额硬币的数量
			minCoin = minCoin % coins[i]; // 求出剩下需要找的钱数
		}
	}
	return count;
}
console.log(minCoinChange(63, [1, 5, 10, 25])); // 6
复制代码

完成这题后,对贪心策略是不是消化了呢?上面说到近似解决问题,也就是说它是有缺陷的,当我们把21美分的硬币加到硬币列表中,执行的结果还是6,然鹅我们知道这时的最优解是3个21美分的硬币。这就说明在贪心策略有些场景下是不适用的,我们在使用时应谨慎。

分而治之策略

分而治之是解决问题的典型策略,它的思想在于将问题分为若干互相独立更小规模的部分,通过解决每一个小规模的问题,并将结果汇总从而得到问题的解。咱们还拿吃自助来做比喻,分治就像是吃自助的时候需要先把菜都端上来,你分配几个服务员(当然现实中是不太现实的),一个去拿肉类、一个去拿海鲜、一个去拿蔬菜、一个去接饮料......最后放在一起开吃,他们之间拿东西是互相独立的。下面我们用分治策略来解一下上面的最小硬币找零问题

function minCoinChange(amount, coins) {
	let minCoin = amount;
	if (coins.includes(amount)) { // 终止条件
		return 1; // 需找钱数正好为面额
	} else {
		for (let i = 0; i < coins.length; i++) {
			if (coins[i] <= minCoin) {
				let newMin = 1 + minCoinChange(amount - coins[i], coins); // 计算减去一个当前面额硬币后剩下钱的最少硬币数
				if (newMin < minCoin) {
					minCoin = newMin;
				}
			}
		}
	}
	return minCoin;
}
console.log(minCoinChange(63, [1, 5, 10, 25])); // 6
console.log(minCoinChange(63, [1, 5, 10, 21, 25])); // 3
复制代码

我们又用分而治之的策略来解决了这道题,将问题规模缩小并相互独立。我们发现它的能力是比较全面的,就算加入了21美分硬币的情况下,依旧能算出最优解。但是他的超多次递归严重影响了性能,而且会出现很多的重复计算,我们想个办法来给它小优化一下,使用一个记忆化方法——即用一个数组来把小规模问题结果给记录下来,下次再次需要计算的时候,先查找数组中是否有结果,有就直接返回,没有再计算,更改后的代码如下

function minCoinChange(amount, coins, minCoinList) {
	let minCoin = amount;
	if (coins.includes(amount)) { // 终止条件
		return 1;
		minCoinList[amount] = 1; // 记录最小规模问题的解
	} else if (minCoinList[amount]) { // 查找,如果计算过就直接返回
		return minCoinList[amount];
	} else {
		for (let i = 0; i < coins.length; i++) {
			if (coins[i] <= amount) {
				let newMin = 1 + minCoinChange(amount - coins[i], coins, minCoinList);
				if (newMin < minCoin) {
					minCoin = newMin;
					minCoinList[amount] = newMin; // 将小规模问题最优解记录下来
				}
			}
		}
	}
	return minCoin
}
console.log(minCoinChange(63, [1, 5, 10, 21, 25], [])) // 3
复制代码

改进之后,大大提高了算法的性能,这时他们的子问题之间已经产生了联系,子问题依靠子问题的解也就是记忆化对自己进行求解,这样就已经接近动态规划的思想了,但是还不能称其为动态规划,那么什么是动态规划呢?我们继续往下看。

动态规划策略

动态规划也是一种将复杂问题分解成更小的子问题来解决。但是它和分治策略不同的是,首先它分解的子问题之间是相互依赖的,大规模问题的解依赖小规模问题的解,其次它是从最简单最小的规模问题开始解,问题的规模逐渐增大。是一种自底向上求解的方法(分治策略是自顶向下的)。还是吃自助(可能是太久没出去想吃自助了),这次那几个服务员没有进行分类拿取,需要互相看看都拿了什么,拿了多少,自己再决定如何去拿。下面我们用动态规划的解法再来解一下上面的最小硬币找零问题

let list = new Array(64).fill(0); // 初始化一个存储小规模问题解的数组
function coinDynamic(amount, coins, minCoinList) {
	for (let coin = 1; coin < amount + 1; coin++) { // 从小到大求出最优解
		let minCoin = coin;
		for (let j = 0; j < coins.length; j++) {
			if (coins[j] <= coin) {
				let num = 1 + minCoinList[coin - coins[j]]; // 利用小规模的最优解
				if (num < minCoin) {
					minCoin = num;
				}
			}
		}
		minCoinList[coin] = minCoin; // 存储最优解
	}
	return minCoinList[amount];
}
console.log(coinDynamic(63, [1, 5, 10, 21, 25], [list]));
复制代码

可见我们这里用的从小到大进行迭代的方法而非递归,它更有条理而且更高效的解决了这个问题,而且代码也更加简洁。总结一下分治策略和动态规划

  • 它们都是把问题分解为更小规模的问题进行解决
  • 分治策略是自顶向下求解,动态规划是自底向上求解
  • 分治策略的子问题之间是互相独立的,动态规划的子问题之间是互相联系的

小结

本篇通过一道题介绍了三大策略,大家是否更加了解了呢?以上为个人理解,如有错误请及时指出,共同努力,共同进步,如果觉得作者写的还可以,可以给个小赞。加油!!!

关注下面的标签,发现更多相似文章
评论