算法合集之淺析信息學(xué)中的“分”與“合”(編輯修改稿)
2024-11-14 18:36 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 M≤100 [例三 ]最優(yōu)序列 —— “ 分”繁為簡(jiǎn) ?對(duì)于這個(gè)子問(wèn)題，由于 K做了限制，我們可以用動(dòng)態(tài)規(guī)劃來(lái)解決這個(gè)問(wèn)題。 ? 設(shè) dp[i]表示前 i個(gè)元素，在滿(mǎn)足題意的前提下選出的最大和 dp[i]=max(dp[i1],dp[iM]+value[i]) i≥M dp[i]=max(dp[i1],value[i]) 0iM dp[0]=0 [例三 ]最優(yōu)序列 —— 進(jìn)一步分析 子問(wèn)題 原問(wèn)題 是否可以通過(guò)求解 K次的子問(wèn)題從而解決原題呢 ? 1 K [例三 ]最優(yōu)序列 —— 進(jìn)一步分析 ? 命題 原問(wèn)題的解集等價(jià)于由 K組互不相交的子問(wèn)題的解組成的解集。 ? 引理一 原問(wèn)題的任意一組解都可以由 K組不相交的子問(wèn)題的解組成。 ? 引理二 任意 K組不相交的子問(wèn)題的解的并均為原問(wèn)題的解。 [例三 ]最優(yōu)序列 —— 進(jìn)一步分析 ?題目中存在著一個(gè)潛條件，即： 每個(gè)元素只能被選一次 ?若直接套用 K次動(dòng)態(tài)規(guī)劃來(lái)求解，有可
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1