贪心

贪心算法

贪心算法是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获取全局最优解。贪心算法简洁且高效，在许多实际问题中都有着广泛的应用。

贪心算法和动态规划都常用于解决优化问题，它们之间存在着一些相似之处，比如都依赖最优子结构。

• 动态规划会根据过去阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
• 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直到问题被解决。

给定n中硬币，第i中硬币面值为coins[i-1],目标金额为amt，每种硬币都可被重复选取，问能凑出目标金额的最少硬币数量，若无法凑出，返回-1。

/* 凑硬币 */

// 前置条件：coins升序
function cointChangeGreedy(coins = [], amt = 0) {
	if (amt === 0) return -1;
    let i = coins.length - 1;
	// 硬币数量
	count = 0;
	while (amt > 0) {
		// 找到小于且最接近剩余金额的硬币
		while (i > 0 && coins[i] > amt) {
			i -= 1;
		}

		// 选取coint
		amt -= coins[i];
		count += 1;
	}

	return count;
}

let res = cointChangeGreedy([1, 5, 10, 20], 88);
console.log(res);

贪心算法的优点与局限性

贪心算法不仅操作直接、实现简单，而且通常效率较高。然而对于某些硬币面值组合，贪心算法并不能找到最优解，例如下列：

1. 正例：coins=[1,5,10,20,50,100],在该硬币组合下任意的amt都能找到最优解。
2. 反例：coints=[1,20,50],当amt为60时贪心算法会给出50+1x10的组合，共计11枚，但动态规划可以找到最优解20x3，仅需三枚。
3. 反例：coins=[1,49,50],当amt为98时，贪心组合为50+1x49，而动态规划则为49x2.

也就是说对于零钱兑换问题，贪心算法无法保证找到全局最优解，并且有可能找到非常差的解。一般情况下，贪心算法的适用情况分以下两种：

1. 可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效。
2. 可以找到近似最优解：贪心算法在这种情况下也是可用的，对于复制的情况来说，寻找最优解往往非常困难，能以高效找到次优解也是不错的。

贪心算法特性

相较于动态规划，贪心算法的适用条件更为苛刻，其主要关注问题的两个性质。

• 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证获取最优解。
• 最优子结构：原问题的最优解包含子问题的最优解。

贪心算法解题步骤

贪心问题大致可分为三步：

1. 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。
2. 确定贪心策略：确定在每一步中做出贪心选择，这个策略能在每一步减少问题的规模，并最终解决问题。
3. 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。

贪心算法经典例题

• 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解。
• 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解。
• 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得重量不超过载重量，且价值最大。如果每次选择性价比最高的物品，那么贪心算法在一些情况下可以得到最优解。
• 股票买卖问题：给定一组股票的历史价格，你可以进行对此买卖，但如果你已经持有股票，那么在卖出之前不能再购买，目标是获取最大利益。
• 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最低的两个节点合并，最后得到的霍夫曼树的带权路径长度最小。
• Dikjstra算法：它是一种解决给定源订单到其他各顶点的最短路径的贪心算法。

分数背包问题

给定n个物品，第i个物品的重量为wgt[i-1]，价值为val[i-1]，以及一个容量为cap的背包。每个物品只能选取一次，但是可以选择物品的一部分，价值依据选择的重量比例计算，问在有限的背包容量下如何使得背包内的物品价值最高。

/* 分数背包问题 */
function fractionalPack(wgt = [], val = [], cap = 0) {
    // 汇总所有物品
	let tings = [];
	wgt.map((el, index) => {
		let obj = {
			w: el,  // 重量
			v: val[index],  // 总价值
			unit: val[index] / el,  // 单位价值
		};
		tings.push(obj);
	});

    // 排序
	let sortTings = tings.sort((a, b) => b.unit - a.unit);
    console.log(sortTings);
    
	let res = 0; // 总价值
	while (cap > 0) {
		// 选取单位价值最大的物品进行填充
		let max = sortTings[0];

		// 直接占满
		if (max.w > cap) {
			res += cap * max.unit;
			cap = 0;
		} else {
			// 未占满
			res += max.v;
			cap -= max.w;
            
            sortTings.shift()
		}
	}
	return res;
}

let res = fractionalPack([20, 40, 10, 30, 50], [120, 210, 50, 150, 240], 50);

console.log(res);

最大容量问题

输入一个数组ht，其中每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。容器的容量等于高度和宽度的乘积，其中的高度由较短的隔板控制，宽度是两个隔板的索引之差。请在数组中选择两个隔板，使得组成的容器容量最大，返回最大容量。

思考：只有向内收缩较短隔板，才有可能使得容量变大。

/* 最大容量问题 */
function maxCapcity(ht = []) {
	// 定义i，j使其分布数组两端
	let i = 0,
		j = ht.length - 1;

	let res = 0;
	while (i < j) {
		// 计算容量
		let cap = Math.min(ht[i], ht[j]) * (j - i);
		// 存储最大
		res = Math.max(res, cap);

		// 移动隔板
		if (ht[i] > ht[j]) {
			j--;
		} else {
			i++;
		}
	}
	return res;
}

let res = maxCapcity([3, 8, 5, 2, 7, 7, 3, 4]);
console.log(res);

最大切分乘积问题

给定一个正整数n，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少？

/* 最大切分乘积：贪心 */
function maxProductCutting(n) {
    // 当 n <= 3 时，必须切分出一个 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // 贪心地切分出 3 ，a 为 3 的个数，b 为余数
    let a = Math.floor(n / 3);
    let b = n % 3;
    if (b === 1) {
        // 当余数为 1 时，将一对 1 * 3 转化为 2 * 2
        return Math.pow(3, a - 1) * 2 * 2;
    }
    if (b === 2) {
        // 当余数为 2 时，不做处理
        return Math.pow(3, a) * 2;
    }
    // 当余数为 0 时，不做处理
    return Math.pow(3, a);
}

let res = maxProductCutting(8)
console.log(res)