HDU 1712 ACboy needs your help AC男需要你的帮助 （分组的背包）

 

分组背包问题：有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

 

题意：

　　要用m天的时间来学n门课程，给出一个v[n][m]的矩阵，v[i][j]代表的是花j天的时间学习第i门课程所获得的价值，求能获得的最大价值？（当然同一门课不可多次修读）

 

思路：

　　很裸的分组背包。有点类似于01背包，那就转成01背包的思想。

　　第1层循环是“组”，第2层循环是当前背包容量（即m天），第3层循环是该组内的每件物品。说点容易懂的话，每组中只能选1件，那么有多少组就是最多就是多少件了，但是由于背包容量的限制，可能放不下这么多件，那还得再考虑一下搭配问题，所以任意一组也可以不选。那么问题就是在第 i 组中挑还是不挑，若挑，要挑哪一件的问题了？

看伪码（这样可以保证同组至多挑一件）：

for 所有的组k　　//组

    for v=V..0　　//当前背包容量

        for 所有的物品i属于组k　　//组内物品

            f[v]=max{f[v],f[v-c[i]]+w[i]}　　//时刻要保证v-c[i]>=0，总不能让数组的下标为负数吧？

　　如果每组仅有1件物品，也就是可以撤掉第3层循环，那么就是01背包了。但是这里由于有每组由任意多件物品，为了保证同组内只装1件，所以先考虑完此组后再考虑别的组；考虑完用没有装此组的状态去更新装了此组的状态。

　78MS

#include <bits/stdc++.h>
#define num 105
using namespace std;
int a[num][num];
int dp[num];
void cal(int n,int m)
{
    int i,j,t;
    for(i=0;i<n;i++)    //组
        for(j=m;j>0;j--)    //当前背包容量
            for(t=1;t<=j;t++)    //同一组内的所有物品，刚好每组m个
                    dp[j]=max( dp[j] , dp[j-t]+a[i][t-1]    );
}
void main()
{
    int n,m,i,j;
    while(scanf("%d%d",&n,&m),n!=0)    //n门课，m天
    {
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                scanf("%d",&a[i][j]);
        cal(n,m);
        printf("%d
",dp[m]);
        memset(a,0,sizeof(a));    //清内存。
        memset(dp,0,sizeof(int)*(m+1));    //清内存    
    }
}