该题要用分组背包做，这里就是要怎样处理0必须选，1最多选一个，2任意选的问题；
这里我们就开个二维数组；f[i][j]，i表示第组，j表示时间；当该组为0时，我们在该组的选择可以来自上一组的结果，也可以来自该组的结果；
如果为1那么结果只能依赖上一组的结果，如果依赖本组那么就会造成该组会多选；
为2是那就是一个01背包；
View Code #include#include #include using namespace std; class node { public: int cost,happy; }; class Node { public: node t[124]; int type,N; }; Node T[124]; int Max( int a, int b ) { return a > b ? a : b; } int DP( int n , int time ) { int f[124][124]; memset( f , -1 , sizeof( f ) ); memset( f[0] , 0 ,sizeof(f[0]) ); for( int i = 1 ; i <= n ; i ++ ) { switch( T[i].type ) { case 0: for( int j = 0 ; j < T[i].N; j++ ) for( int k = time ; k >= T[i].t[j].cost ; k-- ) { if( f[i][k-T[i].t[j].cost]!=-1 ) f[i][k] = Max(f[i][k],f[i][k-T[i].t[j].cost] + T[i].t[j].happy); if( f[i-1][k-T[i].t[j].cost]!=-1 ) f[i][k] = Max(f[i][k],f[i-1][k-T[i].t[j].cost] + T[i].t[j].happy); } break; case 1: for( int j = 0 ; j < T[i].N; j++ ) for( int k = time ; k >= 0 ; k-- ) { f[i][k] = Max(f[i-1][k],f[i][k]); if( k-T[i].t[j].cost>=0&&f[i-1][k-T[i].t[j].cost] != -1 ) f[i][k] = Max( f[i][k],f[i-1][k-T[i].t[j].cost] + T[i].t[j].happy ); } break; case 2: for( int j = 0 ; j <= time ; j++) { f[i][j] = f[i-1][j]; } for( int j = 0 ; j < T[i].N; j++ ) for( int k = time ; k >= 0 ; k-- ) { if( k-T[i].t[j].cost>=0&&f[i][k-T[i].t[j].cost]!=-1 ) f[i][k] = Max(f[i][k], f[i][k-T[i].t[j].cost] + T[i].t[j].happy); } break; } } return f[n][time]; } int main( ) { int n , m , time, type; while( scanf( "%d%d",&n , &time )==2 ) { for( int i = 1 ; i <= n ; i++ ) { scanf( "%d%d",&T[i].N, &T[i].type ); for( int j = 0 ; j < T[i].N ; j++ ) { scanf( "%d%d",&T[i].t[j].cost , &T[i].t[j].happy ); } } printf("%d\n", DP( n , time )); } return 0; }