【愚公系列】软考中级-软件设计师 056-算法设计与分析（动态规划法和贪心法）

大家好，欢迎来到IT知识分享网。

🚀前言

动态规划法（Dynamic Programming）和贪心法（Greedy Algorithm）是两种常用的问题求解方法。它们在某些情况下可以互相替代，但在其他情况下则各有优势。

动态规划法是一种将大问题拆分成更小的子问题，并将子问题的解存储起来以避免重复计算的方法。它通常用于求解具有重叠子问题和最优子结构性质的问题。动态规划法的基本思想是，通过解决子问题找到问题的最优解，然后将子问题的解合并起来得到原问题的最优解。动态规划法的时间复杂度通常为O(n^2)或更低，但空间复杂度可能较高。

贪心法是一种贪心地进行选择，每次选择当前最优解的方法。贪心法通常适用于具有贪心选择性质的问题，即每一步都选择当前最优解能够得到全局最优解。贪心法的优点是简单且高效，时间复杂度通常为O(n)。然而，贪心法不能保证求解得到的解是全局最优解，因此在某些情况下可能会得到次优解或错误解。

动态规划法和贪心法的比较可以从以下几个方面进行：

1. 解决问题的类型：动态规划法适用于具有重叠子问题和最优子结构性质的问题，而贪心法适用于具有贪心选择性质的问题。
2. 解决问题的效率：动态规划法通常需要存储子问题的解，因此在空间上可能比较占用内存。而贪心法不需要存储子问题的解，因此在空间上相对较为节省。在时间效率上，动态规划法的时间复杂度通常为O(n^2)或更低，而贪心法的时间复杂度通常为O(n)。
3. 解决问题的保证性：动态规划法可以保证求解得到的解是全局最优解，而贪心法不能保证。因此，在需要保证求解结果为最优解的情况下，应使用动态规划法。

动态规划法和贪心法在解决问题时各有优势，应根据具体问题的性质选择合适的方法。如果问题具有重叠子问题和最优子结构性质，并且需要求解得到的是全局最优解，则应使用动态规划法。如果问题具有贪心选择性质，并且求解的结果不需要是全局最优解，则可以考虑使用贪心法。

🚀一、动态规划法

🔎1.概念

总结：动态规划一定是具备了以下三个特点：

• 把原来的问题分解成了几个相似的子问题。（强调“相似子问题”）
• 所有的子问题都只需要解决一次。（强调“只解决一次”）
• 储存子问题的解。（强调“储存”）

🔎2.案例

左下图是使用递归来求解的写法，显然，这是一个非常低效的方法，因为其中有大量的重复计算。并且不满足动态规划的第二个特点：“所有的子问题都只需要解决一次“，这个问题很好解决，我们只需要利用动态规划的第三个特点：”储存子问题的解“就可以了。比如，如果已经计算过Fibonacci(3)，那么把结果储存起来，其他地方碰到需要求Fibonacci(3)的时候，就不需要计算，直接调用结果就行。这样做之后，蓝色表示需要进行计算的，白色表示可以直接从存储中取得结果的：

🚀二、贪心法

🔎1.概念

贪心法：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

局部贪心，只针对当前的步骤取最优，而非整体考虑。

判断此类算法，就看算法是否是每一步都取最优，并且整体题意没有透露出最终结果是最优的。

🔎2.案例

贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。在这里我们发现，贪心是一种只考虑眼前情况的策略。

🚀三、动态规划法结合贪心法

🚀四、案例

🔎1.背包问题

题目：考虑一个有n=5个物品的背包问题实例，背包的容量m=10，v(价值)=(6,3,5,4,6)，并且w(重量)=(2,2,6,5,4)，请问不超过sw（背包能承受的总重）的情况下，最大的放入价值是多少（）

🦋1.1 0-1背包问题

public class Main { 
     public static void main(String[] args) { 
     int n = 5; int[] w = { 
    2,2,6,5,4}; int[] v = { 
    6,3,5,4,6}; int sw = 10; int[][] dp = new int[n][sw + 1]; for (int i = 0; i <= sw; i++) { 
     if (i < w[0]) { 
     dp[0][i] = 0; } else { 
     dp[0][i] = v[0]; } } for (int i = 1; i < n; i++) { 
     for (int j = 0; j <= sw; j++) { 
     if (j < w[i]) { 
     dp[i][j] = dp[i-1][j]; } else { 
     dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j- w[i]] + v[i]); } } } System.out.println(dp[n-1][sw]); } } 

🦋1.2 完全背包问题

按价值重量比从大到小：x1、x2、x5、x3、x4

上界：按重量比从大到小放进去，x1、x2、x5都可以，直到x3时，背包剩余容量2、总价值为15，若将背包填满，则将x3放入重量为2即1/3，此时背包内总价值为15+5*1/3=16.67；下界：每次放入价值最大的，直至放不进去，即6+6=12

🔎2.运输问题

🔎3.消防栓问题

🚀感谢：给读者的一封信

亲爱的读者，

我在这篇文章中投入了大量的心血和时间，希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验，我相信这些信息对您非常有帮助。

如果您觉得这篇文章对您有所帮助，我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担，但它会对我继续创作高质量的内容产生积极的影响。

我之所以写这篇文章，是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命，也鼓励我花更多的时间和精力创作更多有价值的内容。

如果您愿意支持我的创作，请扫描下面二维码，您的支持将不胜感激。同时，如果您有任何反馈或建议，也欢迎与我分享。

再次感谢您的阅读和支持！

最诚挚的问候， “愚公搬代码”