當前位置:成語大全網 - 新華字典 - 背包問題提問方式的變化

背包問題提問方式的變化

上面提到的各種背包問題都要求在背包容量(費用)的限制下能夠獲得最大值,但是背包問題有很多靈活的提問方式,這裏值得壹提。但我認為,只要深刻理解背包問題求最大值的方法,即使問題方法變了,想出壹個算法也不難。

比如搞清楚最多能放多少物品或者最多能裝多少背包。這些都可以根據具體問題,用前面的方程求所有狀態(F數組)的值來得到。

另外,如果要求是“最小總值”和“最小總件數”,只需將上述狀態轉移方程中的max改為min即可。

這裏有壹些更多樣的問題。壹般來說,背包問題需要壹個最優值。如果需要輸出這個最優值,可以參考壹般動態規劃問題輸出方案的方法:記錄狀態轉移方程的哪壹項是每個狀態的最優值,換句話說,記錄它是從哪個策略導出的。妳可以根據這個策略找到之前的狀態,然後從之前的狀態往前推。

或者以01背包為例,方程為f[v]=max{f[v],f[v-c]+w}。然後用壹個數組g [v],設g[v]=0表示推導f[v]的值時采用方程的前壹項(即f[v]=f[v]),g[v]表示采用方程的後壹項。註意這兩項分別代表兩種策略:第I項不選,第I項選。那麽輸出方案的偽代碼可以寫成如下(設最終狀態為f[N][V]):

i=N

v=V

while(I & gt;0)

if(g[v]==0)

打印機沒有選擇項目I

else if(g[v]==1)

打印選擇的項目I

v=v-c

另外,在輸出方案的過程中也可以根據f[v]的值實時查出方程的前壹項或後壹項,即不需要記錄G數組,上面代碼中的g [v]==0改為F [v] = = F,g[v]==1改為F [v] = = F。

具有最小輸出字典序的最優方案

這裏,“字典順序最小”是指在項目1的選擇方案之後字典順序最小...n排列。以輸出01背包最小字典序的方案為例。

壹般來說,要找到壹個字典序最小的最優方案,只需要註意轉移時的策略就可以了。首先,子問題的定義要稍微改壹下。我們註意到,如果存在壹個具有1項的最優方案,那麽答案壹定包含1項,原問題轉化為背包容量為v-c[1]且項為2的子問題..n .另壹方面,如果答案不包含1項,則轉化為背包容量為V,項為2的子問題..n .無論答案是什麽,子問題項都以I的形式定義..n而不是1..如上所述,所以狀態的定義和轉移方程需要改變。但也許先將項目逆序排列更容易,下面將根據項目已經逆序排列的事實進行描述。

在這種情況下,可以按照經典的狀態轉移方程進行評估,但需要註意的是,從n到1輸入時,如果f[v]==f和f[v]==f[f-c]+w都為真,則應該按照後者輸出方案(即選擇第I項)。對於壹個背包問題,給定背包容量,商品成本,以及商品之間的關系(分組,依賴等。),除了給出各物品數值後得到的最大值外,還可以得到裝滿背包或把背包打包到指定容量的方案總數。

對於這類問題,壹般只需要將狀態轉移方程中的max改為sum即可。舉個例子,如果每壹個物品都是01背包中的壹個物品,那麽轉移方程為f[v]=sum{f[v],f[v-c]+w},初始條件為f[0][0]=1。

事實上,之所以可行,是因為狀態轉移方程考察了所有可能的背包構圖方案。這裏的最優方案是指商品總價值最大的方案。還是以01背包為例。

結合求最大總價值和方案總數的思想,可求出最優方案總數如下:f[v]與上述含義相同,g[v]表示該子問題的最優方案總數,因此g[v]的偽碼與f[v]同時求出:

因為i=1..普通

對於v=0..V

f[v]=max{f[v],f[v-c]+w}

g[v]=0

if(f[v]==f[v])

公司(g[v],g[v]

if(f[v]==f[v-c]+w)

inc(g[v],g[v-c])

如果這是妳第壹次看到這樣的問題,請仔細理解上面的偽代碼。顯然,這裏不可能窮盡背包動態規劃問題的所有方法。甚至還有壹類問題是背包動態規劃與其他領域(如數論、圖論)相結合的問題,在這篇關於背包問題的專題文章中就不討論了。但只要深入理解前面提到的所有背包問題的思路和狀態轉移方程,遇到其他變形方法,只要題目難度屬於NOIP,想出算法應該不難。

也應該是壹個OIer應該具備的素質。