算法合集之淺析信息學(xué)中的“分”與“合”-免費(fèi)閱讀
【正文】 ?所有點(diǎn) i向點(diǎn) (i+1)連邊，容量為 +∞ ，費(fèi)用為 0 ?源 S向所有點(diǎn) i各連一條邊，容量為 +∞，費(fèi)用為 0 ?所有點(diǎn) i’ 向匯 T各連一條邊，容量為 +∞，費(fèi)用為 0 ?所有點(diǎn) i’ 向點(diǎn) (i+M)連邊，容量為 +∞ ，費(fèi)用為 0 3’ 2’ 1’ …… n’ 1 2 3 n T S …… 容量 = 1 費(fèi)用 = value[i] +∞ 0 [例三 ]最優(yōu)序列 —— 整體分析 ?構(gòu)圖完成之后，網(wǎng)絡(luò)中的每個(gè)單位流量表示一個(gè)子問(wèn)題的解，因此，我們只需要在網(wǎng)絡(luò)中尋找 K次最大費(fèi)用增廣路即可得到答案。 ?要求選出的元素之和最大。 ?合 ?“合”的思想與“分”相對(duì)，是將一些零散的小問(wèn)題的解決合并成一個(gè)大問(wèn)題，從而取得整個(gè)問(wèn)題的解決。 ?要求選出的元素之和最大。 [例三 ]最優(yōu)序列 —— 進(jìn)一步分析 ?題目中存在著一個(gè)潛條件，即： 每個(gè)元素只能被選一次 ?若直接套用 K次動(dòng)態(tài)規(guī)劃來(lái)求解，有可能導(dǎo)致某個(gè)元素被取多次，無(wú)法滿(mǎn)足題目中的這個(gè)條件。 謝 謝 。 ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1