發(fā)現(xiàn)問題的起因是HDU 1712，一個赤裸的分組背包。所以有必要說一下這個題目。
題意：
一個學(xué)生用M天的時間復(fù)習(xí)N門課程，每門課程花費不同的天數(shù)，有不同的收獲。問如何安排這M天，使得收獲最大。
思路：
可以將每一門課看成一個分組，每門課不同天數(shù)的選擇看成是分組的物品（顯然只能有一個選擇），物品的費用即為花費的天數(shù)，物品的價值為題中給出的收獲。該題中背包容量最大為M。
設(shè)dp[x]為前i組物品，在背包容量為x（即費用為x）時的最大價值。則將i從1到N進(jìn)行過歷遍后（第一重循環(huán)），dp[m]即為所求。
在這種狀態(tài)設(shè)置中，容易想出以下兩種階段遞推方式（以下所述都為第二和第三重循環(huán)）：
1，在同一個背包容量中，對不同費用的物品進(jìn)行枚舉比較：
for(j=MAX;j>=1;--j) //背包容量
for(k=1;k<=m;++k) //不同費用的物品
2，在同一費用的物品中，對放在不同背包容量時計算最大價值：（該方式同《背包九講-分組背包》中的偽代碼部分）
for(k=1;k<=m;++k) //不同費用的物品
for(j=MAX;j>=1;--j) //背包容量
簡略分析：
1，分析第一種遞推方式的正確:
該方式即求在容量為j的背包中，選擇哪一個物品可以有最大價值。
看遞推方程：dp[j]=max(dp[j],dp[j-c[k]]+w[k]);（其中c[k]為k物品的費用，w[k]為價值），由于遞降枚舉背包容量，max比較中的dp[j]是由上一組物品決策所得，在這里將被忽略。因為就算不忽略，在本組物品中dp[j]的決策依然要取決于dp[j-c[k]]+w[k]。
而同樣由于遞降枚舉背包容量（第二重循環(huán)），dp[j-c[k]]在本組物品中是未進(jìn)行過決策的，亦即背包容量為j-c[k]時，在本組物品中是沒有選擇任何物品的，這可以保證對dp[j]決策時，不會多選本組中的物品。
2，分析第二種遞推方式的錯誤：
該方式即求對物品k，放在所有背包中，計算各個最大價值。
同樣是遞推方程：dp[j]=max(dp[j],dp[j-c[k]]+w[k]);（其中c[k]為k物品的費用，w[k]為價值）。能否保證dp[j-c[k]]在本組中未經(jīng)決策，就成了該遞推方式對錯的關(guān)鍵。
由于背包容量的遞降枚舉在第三重循環(huán)，只能保證k物品不會重復(fù)選擇。對于另一k0物品，當(dāng)背包容量枚舉到j(luò)-c[k]的時候，由方程可以有：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了那個題目，但是感覺留下了一堆的問題。然后忙了兩天別的事，直到今天才感覺徹底搞懂了。
在最近的幾個題中，也算逐漸明白知識學(xué)習(xí)與能力培養(yǎng)的區(qū)別。
----------------------------------------------------------------------------------------------------------------------
以下附《背包九講-分組背包》中的內(nèi)容和HDU 1712的代碼。
分組背包：
P06: 分組的背包問題
問題
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
算法
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設(shè)f[k][v]表示前k組物品花費費用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中“一個簡單有效的優(yōu)化”。
小結(jié)
分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉(zhuǎn)化為分組的背包問題（例如P07），由分組的背包問題進(jìn)一步可定義“泛化物品”的概念，十分有利于解題。
----------------------------------------------------------------------------------------------------------------------
//HDU 1712(被注釋的為以上第二種遞推方式）：
#include <iostream>
using namespace std;
const int MAX=100;
int dp[MAX+1],data[MAX+1][MAX+1];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&(n||m))
{
int i,j,k;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
scanf("%d",&data[i][j]);
/*
memset(dp,0,sizeof(dp));
for(i=1;i<=n;++i)
for(j=m;j>=1;--j)
for(k=MAX;k>=j;--k)
if(dp[k]<dp[k-j]+data[i][j])
dp[k]=dp[k-j]+data[i][j];
*/
memset(dp,0,sizeof(dp));
for(i=1;i<=n;++i)
for(j=MAX;j>=1;--j)
for(k=1;k<=m;++k)
if(j>=k)
dp[j]=dp[j]>dp[j-k]+data[i][k]?dp[j]:dp[j-k]+data[i][k];
printf("%d\n",dp[m]);
}
return 0;
}