高校问答琵琶记的结构特点:极差算法的优缺点是什么？
来源：百度文库 编辑：高校问答 时间：2024/04/26 01:28:03
希望能举例说明。
朋友看看这个,对你有没有用,
以下是极差问题可用贪婪算法的一点资料，请斟酌：
下面我们以求max为例来讨论此题用贪心策略求解的合理性。
讨论：假设经（N－3）次变换后得到3个数：a,b,max’（max’≥a≥b），其中max’是（N－2）个数经（N－3）次f变换后所得的最大值，此时有两种求值方式，设其所求值分别为， ，则有： ＝（a×b＋1）×max’＋1， ＝（a×max’＋1）×b+1 所以 － ＝max’－b≥0若经（N－2）次变换后所得的3个数为：m，a，b（m≥a≥b）且m不为（N－2）次变换后的最大值，即m＜max’则此时所求得的最大值为： ＝（a×b+1）×m+1 此时 － ＝（1+ab）（max’－m）＞0 所以此时不为最优解。
所以若使第k（1≤k≤N－1）次变换后所得值最大，必使（k－1）次变换后所得值最大（符合贪心策略的特点2），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数p，q施加f操作：p←p×q+1，q←∞即可（符合贪心策略特点1），因此此题可用贪心策略求解。讨论完毕。
在求min时，我们只需在每次变换的数列中找到两个最大数p，q施加作用f：p←p×q+1，q←-∞即可．原理同上。