algorithm - 贪婪与动态

Question

我有一些关于算法的一般性问题，当你有一些问题并且你想编写一些算法时，你如何解决这个问题，你如何决定使用哪种算法使用贪婪算法或动态规划？提前致谢

Answer 1

一般来说，我尝试将新问题转换为具有众所周知解决方案的众所周知的问题。然后选择正确的算法是微不足道的。根据我的经验，这涵盖了野外的大多数情况。

如果第一步失败，我会尝试一种贪婪的方法并尝试证明它不起作用。证明部分可能很棘手，但基本上你必须证明在某个中间步骤中的局部最佳选择不会产生整体最佳结果。从那里我开始分支，通常动态是我尝试的第一个替代方案之一。

如果一切都失败了，我开始寻找足够接近手头问题的良好近似算法。许多问题可以在很短的时间和资源中用近似值“足够好”地解决，使其成为明显的赢家。

Answer 2

如果贪心算法可行，我会更喜欢，如果不是，那么如果动态编程可行，那么选择那个，否则渐近行为更差。

你怎么能认真地期望得到你的问题的答案？

所有动态规划任务都有一个特点，即（精心选择的）子问题的最优解也是整个问题最优解的一部分。你要么发现了问题的这个特征，要么你没有……

更新：我想告诉你一个很好的答案，“我将它映射到一个类似的众所周知的问题”，但这不是我所做的。我解决了几个 DP 问题，从那时起，如果我看到使用蛮力算法会产生 O(2^n) 的东西，我会自动开始搜索可以构建最佳解决方案的子问题。