网络上题解很多。我就不乱说了。
首先分组背包的原型：
给物品分组，容量为V的背包，每个分组内的物品互斥，每个分组最多取一个物品。求最大值。
代码很简单：
for( int i=0;i<group;i++ )
for( int j=V;j>=0;j-- )
for( int k=0;k<total[i];k++ )f[V]=max( f[V],f[V-cost[k]]+value[k] );背包九讲里面有，相信大家都看了。不多说。
而这题，是在每个分组中最少取一种物品。
so~ 不能用一维了，+一个维度来表示分组。当前分组会对下一分组有影响。
so DP方程为：当前的01背包，上一组的01背包....；两次去最值就好了。
Code：
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;struct node
{int group,cost,value;
}good[111];
bool cmp( node a,node b ){ return a.group<b.group; }
int max( int a,int b ){ return a>b?a:b; }
int min( int a,int b ){ return a<b?a:b; }
int main()
{int N,G,V;int f[11][11111];while( scanf( "%d %d %d",&N,&V,&G )!=EOF ){memset( f,0,sizeof(f) );for( int i=0;i<N;i++ )scanf( "%d %d %d",&good[i].group,&good[i].cost,&good[i].value );sort( good,good+N,cmp );int j=0;for( int i=0;i<N;i++ )for( int k=V;k>=good[i].cost;k-- ){int g=good[i].group;int c=good[i].cost;int v=good[i].value;f[g][k]=max( f[g][k],f[g][k-c]+v );f[g][k]=max( f[g][k],f[g-1][k-c]+v );}if( f[G][V] )printf( "%d\n",f[G][V] );elseprintf( "Impossible\n" ); }return 0;
}