改
进之路:从贪心到动态规划 贪心算法一直以来都是求解最优问题的一种经典算法,但它在某些问题的求解上可能会出现偏差。
这时候就需要用到另一种常见的算法——动态规划。
动态规划算法主要思想是将原来的问题分解成若干个子问题,然后通过求解子问题的最优解来推导出原问题的最优解。
而贪心算法则是每一步都选择当前状态下的最优解,但不能保证一定是全局最优解。
以背包问题为例,如果我们用贪心算法求解时,每次都优先选取单位重量价值最高的物品放入背包中。
但实际上,有可能存在某个物品的重量很大,导致背包没法放下更有价值的物品。
而在动态规划算法中,我们会预先计算出前n个物品对应每个子背包容量时的最优解,通过逐步增加物品的方式来比较当前步骤的最优解。
这样就能够找到全局的最优解。
虽然动态规划算法需要预先计算出多个子问题的解,但相较于贪心算法,它更具有全局优化的保障。
在某些情况下,贪心算法能够快速求得最优解,但无法保证结果的正确性。
因此我们需要在不同问题中合理选择算法,以得到最优的解决方案。