關于01背包求第k優解

求次優解、第K優解

對于求次優解、第K優解類的問題，如果相應的最優解問題能寫出狀态轉移方程、用動态規劃解決，那麼求次優解往往可以相同的

複雜度解決，第K優解則比求最優解的複雜度上多一個系數K。

其基本思想是将每個狀态都表示成有序隊列，将狀态轉移方程中的max/min轉化成有序隊列的合并。這裡仍然以01背包為例講解一下。

首先看01背包求最優解的狀态轉移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第K優解，那麼狀态f[i][v]就應該是一個大小為K的數組f[i][v][1..K]。其中f[i][v][k]表示前i個物品、背包大小為v時，第k優解的值。“f[i][v]是一個大小為K的數組”這一句，熟悉C語言的同學可能比較好了解，或者也可以簡單地了解為在原來的方程中加了一維。顯然f[i][v][1..K]這K個數是由大到小排列的，是以我們把它認為是一個有序隊列。

我每天都在努力,隻是想證明我是認真的活着.