关键词:
贪心算法是一种很常见的算法思想,而且很好理解,因为它符合人们一般的思维习惯。下面我们由浅入深的来讲讲贪心算法。
找零问题
我们先来看一个比较简单的问题:
假设你是一个商店老板,你需要给顾客找零n元钱,你手上有的钱的面值为:100元,50元,20元,5元,1元。请问如何找零使得所需要的钱币数量最少?例子:你需要找零126元,则所需钱币数量最少的方案为100元1找,20元1张,5元1张,1元1张。
这个问题在生活中很常见,买东西的时候经常会遇到,那我们一般是怎么思考的呢?假设我们需要找零126元,我们先看看能找的最大面值是多少,我们发现126比100大,那肯定可以找一张100块,然后剩下26元,再看26能匹配的最大面值是多少,发现是20,那找一张20的,还剩6块,同样的思路,找一张5块的和1块的。这其实就是贪心算法的思想,每次都很贪心的去找最大的匹配那个值,然后再找次大的。这个算法代码也很好写:
const allMoney = [100, 50, 20, 5, 1]; // 表示我们手上有的面值
function changeMoney(n, allMoney)
const length = allMoney.length;
const result = []; // 存储结果的数组,每项表示对应面值的张数
for(let i = 0; i < length; i++)
if(n >= allMoney[i])
// 如果需要找的钱比面值大,那就可以找,除一下看看能找几张
result[i] = parseInt(n / allMoney[i]);
n = n - result[i] * allMoney[i]; // 更新剩下需要找的钱
else
// 否则不能找
result[i] = 0;
return result;
const result = changeMoney(126, allMoney);
console.log(result); // [1, 0, 1, 1, 1]
贪心算法
上面的找零问题就是贪心算法,每次都去贪最大面值的,发现贪不了了,再去贪次大的。从概念上讲,贪心算法是:
从上面的定义可以看出,并不是所有问题都可以用贪心算法来求解的,因为它每次拿到的只是局部最优解,局部最优解组合起来并不一定是全局最优解。下面我们来看一个这样的例子:
背包问题
背包问题也是一个很经典的算法问题,题目如下:
有一个小偷,他进到了一个店里要偷东西,店里有很多东西,每个东西的价值是v,每个东西的重量是w。但是小偷只有一个背包,他背包总共能承受的重量是W。请问怎么拿东西能让他拿到的价值最大?
其实背包问题细分下来又可以分成两个问题:0-1背包和分数背包。
0-1背包:指的是对于某个商品来说,你要么不拿,要么全拿走,不能只拿一半或者只拿三分之二。可以将商品理解成金砖,你要么整块拿走,要么不拿,不能拿半块。分数背包:分数背包就是跟0-1背包相反的,你可以只拿一部分,可以拿一半,也可以拿三分之二。可以将商品理解成金砂,可以只拿一部分。
下面来看个例子:
这个问题用我们平时的思维也很好想,要拿到总价值最大,那我们就贪呗,就拿最贵的,即价值除以重量的数最大的。但是每次都拿最贵的,是不是最后总价值最大呢?我们先假设上面的例子是0-1背包,最贵的是v1,然后是v2,v3。我们先拿v1, 背包还剩40,拿到总价值是60,然后拿v2,背包还剩20,拿到总价值是160。然后就拿不下了,因为v3的重量是30,我们背包只剩20了,装不下了。但是这个显然不是全局最优解,因为我们明显可以看出,如果我们拿v2,v3,背包刚好装满,总价值是220,这才是最优解。所以0-1背包问题不能用贪心算法。
但是分数背包可以用贪心,因为我们总是可以拿最贵的。我们先拿了v1, v2,发现v3装不下了,那就不装完了嘛,装三分之二就行了。下面我们用贪心来实现一个分数背包:
const products = [
id:1, v: 60, w: 10,
id:2, v: 100, w: 20,
id:3, v: 120, w: 30
]; // 新建一个数组表示商品列表,每个商品加个id用于标识
function backpack(W, products)
const sortedProducts = products.sort((product1, product2) =>
const price1 = product1.v / product1.w;
const price2 = product2.v / product2.w;
if(price1 > price2)
return -1;
else if(price1 < price2)
return 1;
return 0;
); // 先对商品按照价值从大到小排序
const result = []; // 新建数组接收结果
let allValue = 0; // 拿到的总价值
const length = sortedProducts.length;
for(let i = 0; i < length; i++)
const sortedProduct = sortedProducts[i];
if(W >= sortedProduct.w)
// 整个拿完
result.push(
id: sortedProduct.id,
take: 1, // 拿的数量
);
W = W - sortedProduct.w;
allValue = allValue + sortedProduct.v;
else if(W > 0)
// 只能拿一部分
result.push(
id: sortedProduct.id,
take: W / sortedProduct.w,
);
allValue = allValue + sortedProduct.v * (W / sortedProduct.w);
W = 0; // 装满了
else
// 不能拿了
result.push(
id: sortedProduct.id,
take: 0,
);
return result: result, allValue: allValue;
// 测试一下
const result = backpack(50, products);
console.log(result);
运行结果:
0-1背包
前面讲过0-1背包不能用贪心求解,我们这里还是讲讲他怎么来求解吧。要解这个问题需要用到动态规划的思想,关于动态规划的思想,可以看看我这篇文章,如果你只想看看贪心算法,可以跳过这一部分。假设我们背包放了n个商品,W是我们背包的总容量,我们这时拥有的总价值是$D(n, W)$。我们考虑最后一步,
假如我们不放最后一个商品,则总价值为$D(n-1, W)$假设我们放了最后一个商品,则总价值为最后一个商品加上前面已经放了的价值,表示为$v_n + D(n-1, W-w_n)$,这时候需要满足的条件是$ W >= w_n$,即最后一个要放得下。
我们要求的最大解其实就是上述两个方案的最大值,表示如下:
$$ D(n, W) = max(D(n-1, W), v_n + D(n-1, W-w_n)) $$
递归解法
有了递推公式,我们就可以用递归解法了:
const products = [
id:1, v: 60, w: 10,
id:2, v: 100, w: 20,
id:3, v: 120, w: 30
]; // 新建一个数组表示商品列表,每个商品加个id用于标识
function backpack01(n, W, products)
if(n < 0 || W <= 0)
return 0;
const noLast = backpack01(n-1, W, products); // 不放最后一个
let getLast = 0;
if(W >= products[n].w) // 如果最后一个放得下
getLast = products[n].v + backpack01(n-1, W-products[n].w, products);
const result = Math.max(noLast, getLast);
return result;
// 测试一下
const result = backpack01(products.length-1, 50, products);
console.log(result); // 220
动态规划
递归的复杂度很高,我们用动态规划重写一下:
const products = [
id:1, v: 60, w: 10,
id:2, v: 100, w: 20,
id:3, v: 120, w: 30
]; // 新建一个数组表示商品列表,每个商品加个id用于标识
function backpack01(W, products)
const d = []; // 初始化一个数组放计算中间值,其实为二维数组,后面填充里面的数组
const length = products.length;
// i表示行,为商品个数,数字为 0 -- (length - 1)
// j表示列,为背包容量,数字为 0 -- W
for(let i = 0; i < length; i++)
d.push([]);
for(let j = 0; j <= W; j++)
if(j === 0)
// 背包容量为0
d[i][j] = 0;
else if(i === 0)
if(j >= products[i].w)
// 可以放下第一个商品
d[i][j] = products[i].v;
else
d[i][j] = 0;
else
const noLast = d[i-1][j];
let getLast = 0;
if(j >= products[i].w)
getLast = products[i].v + d[i-1][j - products[i].w];
if(noLast > getLast)
d[i][j] = noLast;
else
d[i][j] = getLast;
console.log(d);
return d[length-1][W];
// 测试一下
const result = backpack01(50, products);
console.log(result); // 220
回溯最优解
为了能够输出最优解,我们需要将每个最后放入的商品记录下来,然后从最后往前回溯,将前面的代码改造如下:
const products = [
id:1, v: 60, w: 10,
id:2, v: 100, w: 20,
id:3, v: 120, w: 30
]; // 新建一个数组表示商品列表,每个商品加个id用于标识
function backpack01(W, products)
const d = []; // 初始化一个数组放计算中间值,其实为二维数组,后面填充里面的数组
const res = []; // 记录每次放入的最后一个商品, 同样为二维数组
const length = products.length;
// i表示行,为商品个数,数字为 0 -- (length - 1)
// j表示列,为背包容量,数字为 0 -- W
for(let i = 0; i < length; i++)
d.push([]);
res.push([]);
for(let j = 0; j <= W; j++)
if(j === 0)
// 背包容量为0
d[i][j] = 0;
res[i][j] = null;
else if(i === 0)
if(j >= products[i].w)
// 可以放下第一个商品
d[i][j] = products[i].v;
res[i][j] = products[i];
else
d[i][j] = 0;
res[i][j] = null;
else
const noLast = d[i-1][j];
let getLast = 0;
if(j >= products[i].w)
getLast = products[i].v + d[i-1][j - products[i].w];
if(noLast > getLast)
d[i][j] = noLast;
else
d[i][j] = getLast;
res[i][j] = products[i]; // 记录最后一个商品
// 回溯res, 得到最优解
let tempW = W;
let tempI = length - 1;
const bestSol = [];
while (tempW > 0 && tempI >= 0)
const last = res[tempI][tempW];
bestSol.push(last);
tempW = tempW - last.w;
tempI = tempI - 1;
console.log(d);
console.log(bestSol);
return
totalValue: d[length-1][W],
solution: bestSol
// 测试一下
const result = backpack01(50, products);
console.log(result); // 220
上面代码的输出:
数字拼接问题
再来看一个贪心算法的问题,加深下理解,这个问题如下:
这个问题看起来也不难,我们有时候也会遇到类似的问题,我们可以很直观的想到一个解法:看哪个数字的第一个数字大,把他排前面,比如32和94,把第一位是9的94放前面,得到9432,肯定比32放前面的3294大。这其实就是按照字符串大小来排序嘛,字符大的排前面,但是这种解法正确吗?我们再来看两个数字,假如我们有728和7286,按照字符序,7286排前面,得到7286728,但是这个值没有728放前面的7287286大。说明单纯的字符序是搞不定这个的,对于两个数字a,b,如果他们的长度一样,那按照字符序就没问题,如果他们长度不一样,这个解法就不一定对了,那怎么办呢?其实也简单,我们看看a+b和b+a拼成的数字,哪个大就行了。
假设
a = 728
b = 7286
字符串: a + b = "7287286"
字符串: b + a = "7286728"
比较下这两个字符串, a + b比较大,a放前面就行了, 反之放到后面
上述算法就是一个贪心,这里贪的是什么的?贪的是a + b
的值,要大的那个。在实现的时候,可以自己写个冒泡,也可以直接用数组的sort方法:
const nums = [32, 94, 128, 1286, 6, 71];
function getBigNum(nums)
nums.sort((a, b) =>
const ab = `$a$b`;
const ba = `$b$a`;
if(ab > ba)
return -1; // ab大,a放前面
else if (ab < ba)
return 1;
return 0;
);
return nums;
const res = getBigNum(nums);
console.log(res); // [94, 71, 6, 32, 1286, 128]
活动选择问题
活动选择问题稍微难一点,也可以用贪心,但是需要贪的东西没前面的题目那么直观,我们先来看看题目:
这个问题应该这么思考:为了能尽量多的安排活动,我们在安排一个活动时,应该尽量给后面的活动多留时间,这样后面有机会可以安排更多的活动。换句话说就是,应该把结束时间最早的活动安排在第一个,再剩下的时间里面继续安排结束时间早的活动。这里的贪心其实贪的就是结束时间早的,这个结论其实可以用数学来证明的:
下面来实现下代码:
const activities = [
start: 1, end: 4,
start: 3, end: 5,
start: 0, end: 6,
start: 5, end: 7,
start: 3, end: 9,
start: 5, end: 9,
start: 6, end: 10,
start: 8, end: 11,
start: 8, end: 12,
start: 2, end: 14,
start: 12, end: 16,
];
function chooseActivity(activities)
// 先按照结束时间从小到大排序
activities.sort((act1, act2) =>
if(act1.end < act2.end)
return -1;
else if(act1.end > act2.end)
return 1;
return 0;
);
const res = []; // 接收结果的数组
let lastEnd = 0; // 记录最后一个活动的结束时间
for(let i = 0; i < activities.length; i++)
const act = activities[i];
if(act.start >= lastEnd)
res.push(act);
lastEnd = act.end
return res;
// 测试一下
const result = chooseActivity(activities);
console.log(result);
上面代码的运行结果如下:
总结
贪心算法的重点就在一个贪字,要找到贪的对象,然后不断的贪,最后把目标贪完,输出最优解。要注意的是,每次贪的时候其实拿到的都只是局部最优解,局部最优解不一定组成全局最优解,比如0-1背包,对于这种问题是不能用贪心的,要用其他方法求解。
文章的最后,感谢你花费宝贵的时间阅读本文,如果本文给了你一点点帮助或者启发,请不要吝啬你的赞和GitHub小星星,你的支持是作者持续创作的动力。
欢迎关注我的公众号进击的大前端第一时间获取高质量原创~
“前端进阶知识”系列文章源码地址: https://github.com/dennis-jiang/Front-End-Knowledges
入门必看-算法基础知识讲解小白都也能看得懂(代码片段)
💂个人主页:IT学习日记🤟版权:本文由【IT学习日记】原创、在CSDN首发、需要转载请联系博主💬如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦💅想寻找共同成长的小伙伴,请点击【技... 查看详情
贪心算法讲解及例题
.../a925907195/article/details/41314549 一、概念: 贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固... 查看详情
贪心算法(代码片段)
Java实现贪心算法(找零钱问题)1packagecom.java;23importjava.util.Random;4/**5*贪心算法6*贪心算法,又称贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择。7*也就是说,不从整体最优解出发来考虑,它所做出的仅是在... 查看详情
背包问题(贪心算法)(代码片段)
...这是背包问题,而不是0-1背包问题,背包问题可以用贪心算法进行求解,但0-1无法用贪心算法求解,需要用动态规划算法求解;首先对贪心算法做一下总结,以及它与动态规划算法的区别:贪心算法两个最重要的性质:(1)贪... 查看详情
贪心算法-第一节:贪心算法概述(代码片段)
文章目录一:贪心算法(1)概述(2)特点(3)框架二:典型贪心算法问题(1)无重叠区间①:题目描述②:解题思路③:完整代码(2)活动安排问题①:题目描述... 查看详情
matlab-贪心/贪婪算法(代码片段)
目录一、贪心算法的基本定义和特点二、贪心算法的基本步骤三、实例分析1.问题2.例子与分析3.代码编写(MATLAB版贪心算法)一、贪心算法的基本定义和特点贪心算法的英文是greedyalgorithm,又称贪婪算法,是一种... 查看详情
算法_贪心算法篇(代码片段)
LeetCode_跳跃游戏本文通过跳跃游戏的几个算法例题总结一下相关贪心算法,开始学习的阶段,借鉴好的算法思路并学习,也巩固一下最近学习的算法。(后续遇到贪心算法会续更~~)文章目录LeetCode_跳跃游戏前... 查看详情
算法_贪心算法篇(代码片段)
LeetCode_跳跃游戏本文通过跳跃游戏的几个算法例题总结一下相关贪心算法,开始学习的阶段,借鉴好的算法思路并学习,也巩固一下最近学习的算法。(后续遇到贪心算法会续更~~)文章目录LeetCode_跳跃游戏前... 查看详情
核心算法6贪心算法(代码片段)
贪心算法就是遵循某种既定原则,不断地选取当前条件下最优的选择来构造每一个子步骤的解决方案,直到获得问题最终的求解。在对问题求解时,总是做出在当前看最好的选择。也就是说,不从整体最优上考虑,所做的仅是在... 查看详情
贪心算法(代码片段)
贪心策略 总是做出当前做好的选择。 贪心策略:将问题分成多个子问题;子问题求局部最优解;局部最优解组合成原问题的解。 分类:简单贪心 区间贪心咖啡豆问题 题目描述FatMousepreparedMpoundsofcatfood,readytotrade... 查看详情
bellmanford和spfa算法全解析,从动态规划到队列贪心(代码片段)
文章目录*关于Bellmanford和SPFA算法的详解适用性分析(先看视频)以题代讲蓝桥杯--最短路Bellmanford的动态规划解决(超时,过三个)Bellmanford按边遍历解决(速度竟比SPFA快,我惊了)最终优化--SPFA算法*关于Bellmanford和SPFA算法的详解我是... 查看详情
贪心算法回顾(代码片段)
各位好,贪心算法可以说是处处学到,被面试频频问道,接下来回顾以下,并上代码: 1packagecom.clb.ai.algorithm;23importjava.util.ArrayList;4importjava.util.List;5importjava.util.Map;6importjava.util.TreeMap;78/**9*贪心算法(又称贪婪算法)是指,在... 查看详情
哈夫曼编码--贪心策略(代码片段)
...没有看懂因为比较菜(虽然现在也是很菜的),在《趣学算法》一书中这个问题讲解十分到位,我这篇博客真的是难以望其项背,只能对其进行一点借鉴和摘抄吧哈夫曼编码是一棵树,权值越大的节点越靠近树根,越小的节点就... 查看详情
背包问题(贪心算法)(代码片段)
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法还是比较好理解的一个算法,以前我也... 查看详情
算法-贪心算法详解(代码片段)
...题转换leetcode55跳跃游戏解答题目概述顾名思义,贪心算法或贪心思想采用贪心的策略,保证每次操作都是局部最优的,从而使最后得到的结果是全局最优的。引入钞票支付问题有1元、5元、10元、20元、100元的钞票无... 查看详情
算法笔记贪心算法(代码片段)
前言:对于贪心算法的学习主要以增加阅历和经验为主,也就是多做多积累经验,以下通过几个题目来介绍贪心算法的乐趣!文章目录1.贪心算法基本介绍2.题目题一:给定一个由字符串组成的数组strs,必... 查看详情
图--05---贪心算法prim算法kruskal算法(代码片段)
...生成,如何生成可参考右边的帮助文档文章目录贪心算法贪心算法----定义:使用切分定理找到最小生成树的一条边,不断的重复直到找到最小生成树的所有边贪心算法----原理:最小生成树的算法Prim算法切分规则:... 查看详情
python_分治算法贪心算法动态规划算法(代码片段)
文章目录一、分治算法思想1、基本算法思想2、寻找假币示例二、贪心算法1、思想2、最大不相容活动安排示例三、动态规划1、思想2、最大和路径3、背包问题4、动态规划和贪心算法的区别一、分治算法思想分治算法是一种化繁... 查看详情