HDU OJ 1712 ACboy needs your help [分组背包入门题]

题意：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