网站备案 管局审核 需要多长时间,做购物商城类网站需要,网站建设投标文档,合肥瑶海区医院贪心算法#xff08;Greedy Algorithm#xff09;是一种在每一步选择中都采取在当前状态下最好或最优#xff08;即最有利#xff09;的选择#xff0c;从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。然而#xff0c;要注意的是贪心…贪心算法Greedy Algorithm是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。然而要注意的是贪心算法并不总是能产生全局最优解对于某些问题贪心算法所得的结果可能只是局部最优解。
贪心算法的基本思路
建立数学模型来描述问题首先我们需要把问题抽象化用数学模型来描述。这通常涉及到定义问题的状态、目标函数以及约束条件。 证明贪心选择性质这是使用贪心算法的关键。我们需要证明问题具有贪心选择性质即问题的整体最优解可以通过一系列局部最优选择贪心选择来达到。 设计贪心算法根据贪心选择性质设计出一个逐步构造最优解的贪心算法。 分析算法的正确性证明贪心算法能够得出全局最优解或者在某些情况下至少能得到近似最优解。 贪心算法的特点 贪心性每一步都选择当前状态下的最好或最优解。 局部最优解通过一系列局部最优选择来构造全局最优解。 不能保证全局最优在某些问题中贪心算法可能只能得到局部最优解而不是全局最优解。 背包问题Knapsack Problem 给定一组物品每个物品都有一定的重量和价值要求在不超过背包承重的情况下使得背包内物品的总价值最大。 贪心策略每次选择单位重量价值最高的物品。 注意这种贪心策略并不总是能得到全局最优解。在某些情况下可能需要选择单位重量价值不是最高的物品以达到全局最优。因此背包问题通常使用动态规划来解决。
贪心算法与动态规划的区别
动态规划通常用于求解具有重叠子问题和最优子结构特性的问题。它通过保存子问题的解来避免重复计算从而提高了算法的效率。 贪心算法每一步都做出在当前状态下最好或最优的选择希望通过这些局部最优选择来达到全局最优。它不保存子问题的解因此空间复杂度通常较低。然而它不能保证总是得到全局最优解。 总之贪心算法是一种简单而有效的算法设计技术特别适用于具有贪心选择性质的问题。但在使用时需要注意其局限性避免在不适用的情况下使用贪心算法导致得到错误的解。
附上两道比较好的题目 最短无序连续子数组 class Solution {public int findUnsortedSubarray(int[] nums) {int n nums.length;int maxn Integer.MIN_VALUE, right -1;int minn Integer.MAX_VALUE, left -1;for (int i 0; i n; i) {if (maxn nums[i]) {right i;} else {maxn nums[i];}if (minn nums[n - i - 1]) {left n - i - 1;} else {minn nums[n - i - 1];}}return right -1 ? 0 : right - left 1;}
}
最大数
class Solution {public String largestNumber(int[] nums) {String[] strs new String[nums.length];for (int i 0; i nums.length; i)strs[i] String.valueOf(nums[i]);Arrays.sort(strs, (x, y) - (y x).compareTo(x y));if (strs[0].equals(0))return 0;StringBuilder res new StringBuilder();for (String s : strs)res.append(s);return res.toString();}
}
