Day23:Greedy Algorithm - 贪婪演算法

贪婪演算法（英语：greedy algorithm），又称贪心演算法，是一种在每一步选择中都采取在当前状态下最好或最佳（即最有利）的选择，从而希望导致结果是最好或最佳的演算法。(引用自wikipedia)

情境1:小明有个已经养了三年的小猪扑满里面，某天他心血来潮把小猪宰了，想把里面的零钱(一共29580元)全部拿去银行换成钞票，但是他的皮夹没办法放入太多的钞票，希望银行可以换给他最少数量的钞票，因此在兑换的时候必须优先兑换面额最大的钞票，因此最理想的状况会是:

• 1000元 X 29
• 500元 X 1
• 50元 X 1
• 10元 X 3 

用js来实作:

const exchange = (num) => {
    const money = [1000, 500, 100, 50, 10, 5, 1];
    let point = 0;
    const record = [0, 0, 0, 0, 0, 0, 0];
    while (num > 0) {
        if (num >= money[point]) {
            num -= money[point];
            record[point]++;
        } else {
            point++;
        }
    }
    return record;
};

exchange(29580);

//输出[29, 1, 0, 1, 3, 0, 0]

情境2:潜入珠宝店的小偷带了一个後背包可以负重20kg，因为空间有限，所以他只能挑选最有价值的宝石装进背包，让他可以最大化今晚的获利，可以看到下表有所有的宝石的价格和库存，在挑选宝石除了选最贵的之外还要考量到重量的问题，那麽，就开始来选择要优先带走那些宝石吧!

为了方便计算，所以宝石的重量有灌水一下

1. 先将最贵的一颗钻石放进背包 (背包剩余重量14kg)
2. 接着把一颗红宝石放进背包(背包剩余重量9kg)
3. 蓝宝石有2颗我全都要，通通放进背包(背包剩余重量1kg)
4. 再放一颗祖母绿就好，可…可恶，居然超重了(背包剩余重量-1kg)
5. 不甘心的把祖母绿放回去，放进一颗蛋白石(背包剩余重量0) 大功告成!

本次行动总收益:1000万x1 + 700万x1+ 500万x2 + 100万x1 = 2800万!

像是这类可以利益最大化或是最佳解的的问题很常出现在日常生活中，毕竟大多时候人都是以利益最大化为出发点，思考着该怎麽做才会是最有利的，仔细想想，其实以人类的本性来说，无形之中我们应该用过不少次贪婪演算法了吧!