算法合集之正難則反–淺談逆向思維在解題中的應(yīng)用(編輯修改稿)
2024-11-12 20:32 本頁面
【文章內(nèi)容簡介】 n+M)) 在原集合 Si的模 |Si|不可解的情況下，我們通過可解的 |Si|得到了一個基于容斥原理的算法。 例二、 Greedy Path [題目描述 ] 給定一個有向圖 G=(V,E) 對于 e∈ E,有參數(shù) Ce和 Te,分別表示該條邊的費用與時間。 求一個回路，使得回路中費用總和與時間總和的比值最大。 例二、 Greedy Path 題目是求一條回路，但不是邊權(quán)和最大或者最小，不能直接使用經(jīng)典算法，似乎無從下手。 我們的目標(biāo)是找一條回路 C=(V’ ,E’ ) , 使得F(C)最大： ?????39。39。)(Ee eEe eTCCF例二、 Greedy Path 0*)( ** ??? ?? ?? Ee eEe e TCFC設(shè) S為 G中所有回路組成的集合。 假定 C*=(V*,E*) ∈ S就是我們要求的最優(yōu)回路 ?????***)(Ee eEe eTCCF定義函數(shù) O(t) : ????????39。39。)39。,39。(*m a x)(EeeEeeSEVC TtCtO例二、 Greedy Path 我們做一個猜想 ： 如果有 o (t*)=0， 也就是存在 C* = (V*,E*) ∈ S 滿足 ： ?????***Ee eEe eTCt我們認為 C*就是最優(yōu)回路！ 證明 ： 如果存在另一條回路 C1=(V1,E1) ∈ S更優(yōu)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1