学步园

分组背包，一组最多选一个，可以不选

#include<stdio.h>
#include<string.h>
int dp[102];
int cont[1001][101],v[1001][1001];
int main()
{
    int i,j,k,n,max,m,t;
    while(scanf("%d%d",&n,&m),n||m)
    {
        memset(dp,0,sizeof(dp));
        t=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&cont[i][j]);
                v[i][j]=j;
            }
            for(i=1;i<=n;i++)
              for(j=m;j>=0;j--)
                for(k=1;k<=m;k++)                
                {
                   if(j-v[i][k]>=0)
                   {
                      if(dp[j]<dp[j-v[i][k]]+cont[i][k])
                          dp[j]=dp[j-v[i][k]]+cont[i][k];
                   }
                }
                printf("%d\n",dp[m]);
    }
    return 0;
}