P1757 通天之分组背包 / hdu1712 ACboy needs your help （分组背包入门）

P1757 通天之分组背包

hdu1712 ACboy needs your help

hdu1712题意：A[i][j]表示用j天学习第i个课程能够得到A[i][j]的收益，求m天内获得的收益最大值，一天只能上一节课（转）。

分组背包套路：

for(int i=;i<=组数;++i)

    for(int j=容量;j>=;--j)

        for(int k=;k<=第i组元素个数;++k)

            …………

保证一组只选<=1个

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define re register

 using namespace std;

 int max(int &a,int &b){return a>b?a:b;}

 int n,m,a[][],f[];

 int main(){

     while(~scanf("%d%d",&n,&m)){

         if(!n&&!m) break;

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

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

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

         memset(f,,sizeof(f));

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

             for(re int j=m;j>=;--j)

                 for(re int k=;k<=j;++k)

                     f[j]=max(f[j],f[j-k]+a[i][k]);

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

     }return ;

 }

hdu1712 code

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define re register

 using namespace std;

 int max(int &a,int &b){return a>b?a:b;}

 int n,m,f[];

 int len[],a[][],b[][];

 int main(){

     int q1,q2,q3,mc;

     while(~scanf("%d%d",&m,&n)){

         memset(len,,sizeof(len));

         memset(f,,sizeof(f));

         mc=;

         for(re int i=;i<=n;++i){

             scanf("%d%d%d",&q1,&q2,&q3);

             mc=max(mc,q3);

             a[q3][++len[q3]]=q1;

             b[q3][len[q3]]=q2;

         }

         for(re int i=;i<=mc;++i)

             for(re int j=m;j>=;--j)

                 for(re int u=;u<=len[i];++u)

                     if(j>=a[i][u])

                         f[j]=max(f[j],f[j-a[i][u]]+b[i][u]);

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

     }return ;

 }

P1757 code