//此处收录了各种背包问题的板子，背就完了 
//01背包问题：
//01 bei bao wen ti
//无优化
//wu you hua
for(int i=1;i<=n;i++)
{
    for(int c=0;c<=m;c++)
    {
        f[i][c]=f[i-1][c];
        if(c>=w[i])
        f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
    }
}

//一维数组优化：
//yi wei shu zu you hua

for(int i=1;i<=n;i++)
{
    for(int c=m;c>=0;c--)
    {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
    }
}

//更进一步的常数优化：
//geng jin yi bu de chang shu you  hua
for(int i=1;i<=n;i++)
{
    sumw+=w[i];
    bound=max(m-sumw,w[i]);
    for(int c=m;c>=bound;c--)
    {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
    }
}

//完全背包问题：
//wan quan bei bao wen ti
for(int i=1;i<=n;i++)
{
    for(int c=0;c<=m;c++)
    {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
    }
}

//多重背包问题：
//duo chong bei bao wen ti
for(int i=1;i<=n;i++)
{
    if(w[i]*a[i]>m)
    {
        for(int c=0;c<=m;c++)
        {
        if(c>=w[i])
        f[c]=max(f[c],f[c-w[i]]+v[i]);
        }
    }
    else
    {
         k=1;amount=a[i];
         while(k<amount)
         {
             for(int c=k*w[i];c>=0;c--)
             {
                 if(c>=w[i])
                 f[c]=max(f[c],f[c-w[i]]+k*v[i]);
             }
             amount-=k;
             k<<=1;
         }  
         for(int c=amount*w[i];c>=0;c--)
         {
             f[c]=max(f[c],f[c-w[i]]+amount*v[i]);
         }
    } 
//分组背包问题
//fen zu bei bao wen ti
for(i=1;i<=n;i++)
{
    cin>>w[i]>>z[i]>>x;      //x表示第i个物品的小组编号
    t=max(t,x);      //求小组组数
	b[x]++;      //小组x的物品+1
    g[x][b[x]]=i;      //g[i][j]表示存储小组i中的第j个物品的编号
} 
for(i=1;i<=t;i++){      //小组
    for(j=v;j>=0;j--){      //容量
        for(k=1;k<=b[i];k++){      //小组中的物品
            if(j>=w[g[i][k]]){      //小组i中物品k的容量
                dp[j]=max(dp[j],dp[j-w[g[i][k]]]+z[g[i][k]]);      //状态转移方程
            }
        }
    }
}