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