[go: nahoru, domu]

Skip to content

Commit

Permalink
Update 01.Greedy-Algorithm.md
Browse files Browse the repository at this point in the history
  • Loading branch information
itcharge committed May 13, 2024
1 parent 922939d commit ad0f945
Showing 1 changed file with 2 additions and 2 deletions.
Original file line number Diff line number Diff line change
Expand Up @@ -23,7 +23,7 @@
换句话说,当进行选择时,我们直接做出在当前问题中看来最优的选择,而不用去考虑子问题的解。在做出选择之后,才会去求解剩下的子问题,如下图所示。

![](https://qcdn.itcharge.cn/images/20220511174939.png)
![贪心选择性质](https://qcdn.itcharge.cn/images/20240513163300.png)

贪心算法在进行选择时,可能会依赖之前做出的选择,但不会依赖任何将来的选择或是子问题的解。运用贪心算法解决的问题在程序的运行过程中无回溯过程。

Expand All @@ -37,7 +37,7 @@

也就是说,如果原问题的最优解包含子问题的最优解,则说明该问题满足最优子结构性质。

![](https://qcdn.itcharge.cn/images/20220511175042.png)
![最优子结构性质](https://qcdn.itcharge.cn/images/20240513163310.png)

在做了贪心选择后,满足最优子结构性质的原问题可以分解成规模更小的类似子问题来解决,并且可以通过贪心选择和子问题的最优解推导出问题的最优解。

Expand Down

0 comments on commit ad0f945

Please sign in to comment.