題意：n 代表 共有幾節課， m 代表 天數。
下面是 n*m的矩陣：第 i 行 第 j 個數值代表 第 i 節課 花費 j 天 所得 利益。。求 在所花時間不超過 m 的情況下 怎麼去上課 獲最大利益！
聯系01 背包，差別就是 這個每節課最多只能上一次！！ 就是 矩陣中 每行的 物品 要麼拿一個要麼不拿！！這就是 一個分組背包入門題！！
分組背包： 有N件物品和一個容量為V的背包。 第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可
使這些物品的費用總和不超過背包容量， 且價值總和最大。算法這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品
花費費用v能取得的最大權值， 則有：
f[k − 1][v]
f[k][v] = Max {
f[k − 1][v − c[i]] + w[i]
物品i屬於組k
使用一維數組的偽代碼如下：()
1 for 所有的組k
2 do for v ← V to 0
3 do for 所有的i屬於組k
4 do f[v] = max{f[v],f[v − c[i]] + w[i]}
注意：：這裡的三層循環的順序， “for v=V..0”這一層循環必須在“for 所有的i屬於組k”之外。這樣才能保證每一組內的物品最多只有一個會被添加到背包中。。
AC 代碼：
[cpp]
#include<stdio.h>
#include<string.h>
struct hello
{
int x;
int y;
}ok[10005][10005];
int yi[1000];
int main()
{
int a,b,c,n,m;
while(scanf("%d%d",&n,&m)&&(n+m))
{
memset(yi,0,sizeof(yi));
for(a=1;a<=n;a++)
{ www.2cto.com
for(b=1;b<=m;b++)
{
ok[a][b].x=b;
scanf("%d",&ok[a][b].y);
}
}
for(a=1;a<=n;a++)
{
for(c=m;c>=0;c--)
{
for(b=1;b<=m;b++)
if(c>=ok[a][b].x&&yi[c]<yi[c-ok[a][b].x]+ok[a][b].y)
yi[c]=yi[c-ok[a][b].x]+ok[a][b].y;
}
}
printf("%d\n",yi[m]);
}
return 0;
}
作者：PIAOYI0208
