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=;i<n;i++)    //组

         for(j=m;j>;j--)    //当前背包容量

             for(t=;t<=j;t++)    //同一组内的所有物品，刚好每组m个

                     dp[j]=max( dp[j] , dp[j-t]+a[i][t-]    );

 }

 void main()

 {

     int n,m,i,j;

     while(scanf("%d%d",&n,&m),n!=)    //n门课，m天

     {

         for(i=;i<n;i++)

             for(j=;j<m;j++)

                 scanf("%d",&a[i][j]);

         cal(n,m);

         printf("%d\n",dp[m]);

         memset(a,,sizeof(a));    //清内存。

         memset(dp,,sizeof(int)*(m+));    //清内存

     }

 }

AC代码

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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