贪心算法入门有哪些技巧？

贪心算法的核心思想是通过局部最优解得到或近似取得全局最优解, 此时有几个待解决的问题: 怎么判断题目是否应用贪心策略求解? 怎么寻求局部最优与全局最优的关系? 如何选择最优的贪心标准以得到全局最优/较优解? 思想理解 可以参阅知乎答主"冒泡"的一篇回答 如何理解动态规划? 与 Aditya Bhargava 的算法图解 例题理解 背包问题: 策略选择? 有一个背包, 容量为 150 kg. 有 7 个物品, 要求尽可能让装入背包中物品总价值最大, 且不能超过总容量 请你计算应如何取舍 重量 (kg) 35 30 60 50 40 10 25 价值 ($) 10 40 30 50 35 40 30 对于此题, 贪心的标准可能有几个? 每次选价值最大的 每次选重量最轻的 每次选单位重量价值最高的 试将所有策略与之对应的结果求出如下 策略 1: \(50 + 40 + 40 + 30 = 165 (130 kg)\) 策略 2: \(40 + 30 + 40 + 10 + 35 = 155 (140 kg)\) 策略 3: \(40 + 40 + 30 + 50 + 10 = 170(150kg)\) 哪种是最优解? 策略 3 吗? 如果更改数据呢? 以上三策略都是错的: 要求尽可能让装入背包中物品总价值最大, 且不能超过总容量 题目的局限使得三种策略无对错可分, 原因在于策略 3 打破了题目的限制, 1 和 2 又没有显著的优势可分 因而此题不适合用贪心算法求解, 或者说, 用贪心在此题只能获得近似最优解. 我们解决了第一个问题: 具有某些限制性条件的题目不适合用贪心算法求解 这道题到底怎么解? 应使用动态规划 最优装载问题 给定一个最大载重量为 \(M\) 的卡车和 \(N\) 种食品 有食盐，白糖，大米等 (假设它们都是散装且大货车只受重量限制不受体积限制) 已知第 \(i\) 种食品的最多拥有 \(W_i\) 公斤，其商品价值为 \(V_i\) 元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。