算法合集之《淺析信息學中的“分”與“合”》-全文預覽
【正文】 相交的子問題的解組成。 [例三 ]最優(yōu)序列 —— 整體分析 [例三 ]最優(yōu)序列 —— 整體分析 ?構(gòu)造帶權(quán)網(wǎng)絡(luò) G=(V,A,C) ?序列中的每個元素 i用頂點 i與 i’ 表示， i→i ’ 連邊，容量為 1，費用為該元素的數(shù)值 value[i]，圖中包含源 S與匯 T。 謝 謝 。 ?由于這張圖的邊數(shù)與頂點數(shù)同階，若使用SPFA算法求增廣軌，則期望時間復雜度僅為 O(KN)，是個十分優(yōu)秀的算法。 [例三 ]最優(yōu)序列 —— 進一步分析 ?題目中存在著一個潛條件，即： 每個元素只能被選一次 ?若直接套用 K次動態(tài)規(guī)劃來求解，有可能導致某個元素被取多次，無法滿足題目中的這個條件。 ?數(shù)據(jù)范圍： 1≤N≤1000 1≤M≤100 [例三 ]最優(yōu)序列 —— “ 分”繁為簡 ?對于這個子問題，由于 K做了限制，我們可以用動態(tài)規(guī)劃來解決這個問題。 ?要求選出的元素之和最大。 引言 ? [例一 ]牛奶模版 ? [例二 ]樹的重建 ? [例三 ]最優(yōu)序列 二分
教學課件相關(guān)推薦
鄂ICP備17016276號-1