發(fā)現(xiàn)問題的起因是HDU 1712，一個(gè)赤裸的分組背包。所以有必要說一下這個(gè)題目。

題意：

一個(gè)學(xué)生用M天的時(shí)間復(fù)習(xí)N門課程，每門課程花費(fèi)不同的天數(shù)，有不同的收獲。問如何安排這M天，使得收獲最大。

思路：

可以將每一門課看成一個(gè)分組，每門課不同天數(shù)的選擇看成是分組的物品（顯然只能有一個(gè)選擇），物品的費(fèi)用即為花費(fèi)的天數(shù)，物品的價(jià)值為題中給出的收獲。該題中背包容量最大為M。

設(shè)dp[x]為前i組物品，在背包容量為x（即費(fèi)用為x）時(shí)的最大價(jià)值。則將i從1到N進(jìn)行過歷遍后（第一重循環(huán)），dp[m]即為所求。

在這種狀態(tài)設(shè)置中，容易想出以下兩種階段遞推方式（以下所述都為第二和第三重循環(huán)）：

1，在同一個(gè)背包容量中，對不同費(fèi)用的物品進(jìn)行枚舉比較：

for(j=MAX;j>=1;--j)   //背包容量

      for(k=1;k<=m;++k)  //不同費(fèi)用的物品

2，在同一費(fèi)用的物品中，對放在不同背包容量時(shí)計(jì)算最大價(jià)值：（該方式同《背包九講-分組背包》中的偽代碼部分）

for(k=1;k<=m;++k)    //不同費(fèi)用的物品

      for(j=MAX;j>=1;--j)  //背包容量

簡略分析：

1，分析第一種遞推方式的正確:

該方式即求在容量為j的背包中，選擇哪一個(gè)物品可以有最大價(jià)值。

看遞推方程：dp[j]=max(dp[j],dp[j-c[k]]+w[k]);（其中c[k]為k物品的費(fèi)用，w[k]為價(jià)值），由于遞降枚舉背包容量，max比較中的dp[j]是由上一組物品決策所得，在這里將被忽略。因?yàn)榫退悴缓雎裕诒窘M物品中dp[j]的決策依然要取決于dp[j-c[k]]+w[k]。

而同樣由于遞降枚舉背包容量（第二重循環(huán)），dp[j-c[k]]在本組物品中是未進(jìn)行過決策的，亦即背包容量為j-c[k]時(shí)，在本組物品中是沒有選擇任何物品的，這可以保證對dp[j]決策時(shí)，不會多選本組中的物品。

2，分析第二種遞推方式的錯(cuò)誤：

該方式即求對物品k，放在所有背包中，計(jì)算各個(gè)最大價(jià)值。

同樣是遞推方程：dp[j]=max(dp[j],dp[j-c[k]]+w[k]);（其中c[k]為k物品的費(fèi)用，w[k]為價(jià)值）。能否保證dp[j-c[k]]在本組中未經(jīng)決策，就成了該遞推方式對錯(cuò)的關(guān)鍵。

由于背包容量的遞降枚舉在第三重循環(huán)，只能保證k物品不會重復(fù)選擇。對于另一k0物品，當(dāng)背包容量枚舉到j(luò)-c[k]的時(shí)候，由方程可以有：dp[j-c[k]]=max(dp[j-c[k]],dp[j-c[k]-c[k0]]+w[k0]，亦即dp[j-c[k]]可能在本組中的其他物品中進(jìn)行過決策。

那么這樣就可能導(dǎo)致在一組物品中選擇了多件物品。

----------------------------------------------------------------------------------------------------------------------

周五的早上AC了那個(gè)題目，但是感覺留下了一堆的問題。然后忙了兩天別的事，直到今天才感覺徹底搞懂了。

在最近的幾個(gè)題中，也算逐漸明白知識學(xué)習(xí)與能力培養(yǎng)的區(qū)別。

----------------------------------------------------------------------------------------------------------------------

以下附《背包九講-分組背包》中的內(nèi)容和HDU 1712的代碼。

分組背包：

P06: 分組的背包問題
 問題
 有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。

 算法
 這個(gè)問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設(shè)f[k][v]表示前k組物品花費(fèi)費(fèi)用v能取得的最大權(quán)值，則有f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬于第k組}。

 使用一維數(shù)組的偽代碼如下：

 for 所有的組k
 for 所有的i屬于組k
 for v=V..0
 f[v]=max{f[v],f[v-c[i]]+w[i]}

 另外，顯然可以對每組中的物品應(yīng)用P02中“一個(gè)簡單有效的優(yōu)化”。

 小結(jié)
 分組的背包問題將彼此互斥的若干物品稱為一個(gè)組，這建立了一個(gè)很好的模型。不少背包問題的變形都可以轉(zhuǎn)化為分組的背包問題（例如P07），由分組的背包問題進(jìn)一步可定義“泛化物品”的概念，十分有利于解題。

----------------------------------------------------------------------------------------------------------------------