hdu3033 题目要求与普通的组合背包（每组至多选一个）有所区别，而本题目的话，每组至少选一个，

那么如何保证每组至少选一个呢，问题就在初始化的问题还有状态转移的问题了

if(f[i][l-br[i].b[j]]!=-1 && f[i][l]<f[i][l-br[i].b[j]]+br[i].c[j]) //从当前组再多选一个

                        f[i][l]=f[i][l-br[i].b[j]]+br[i].c[j];

 if(f[i-1][l-br[i].b[j]]!=-1 && f[i][l]<f[i-1][l-br[i].b[j]]+br[i].c[j]) //在上一组的状态下，选当前组的一个

                        f[i][l]=f[i-1][l-br[i].b[j]]+br[i].c[j];

就上面这段关键的代码

 在某一状态存在的情况下（不等于-1），找出三种状态中最大的，赋值给f[i][j] .由于开始时所有f[i][j](i!=0)都为-1，所以更新时一定会从f[0][]开始，而此时就可保证当i=1时，f[i][j]中所有值不为-1的状态一定装了品牌1的某个物品。而当i>1时，

       要想得到 最初 的f[i][j],一定是从已经放有前i-1个品牌的某个状态得到的，而更新最初 的f[i][j] 也一定会用到i品牌的某

       个产品(都可由状态转移方程可知)。

       总之，保证每一类品牌 至少放一件产品是通过赋初值，条件判断，状态转移三方面实现的

 

#include
     
      #include
      
       #include
       
        using namespace std;int n,m,k;__int64 f[11][10010];int num[11];struct brand{    int b[101],c[101];}br[11];int main(){    while(scanf("%d %d %d",&n,&m,&k)==3)    {        int a;        memset(num,0,sizeof(num));        for(int i=0;i
        
         =0;l--)                {                    if(l
        
       
      
     

 

 hdu3535 理解了上面3033之后，这道题目其实也差不多，问题就出在赋初值的问题上了，对了每组至少选一个的情况我们已经知道了，但对于，任意选还有至多选一个的情况，初值当然是复制前一组的状态了，可是，如果不复制前一组的状态，后面的状态转移应该怎么处理，我怎么想也想不透

#include
     
      #include
      
       #define maxn 101#define inf 99999999using namespace std;struct object{	int c,g;};struct sett{	int k,s;	object w[110]; }set[110];int T,n,m,dp[110][maxn];int main(){	while(scanf("%d %d",&n,&T)==2)	{		for(int i=1;i<=n;i++)			for(int j=0;j<=T;j++)				dp[i][j]=-inf;		for(int i=1;i<=n;i++)		{			scanf("%d %d",&set[i].k,&set[i].s);			for(int j=0;j
       
        =set[i].w[j].c;t--)						 { 			                 int v=set[i].w[j].c,cost=set[i].w[j].g;							 int last=dp[i-1][t-v]+cost;							 int cur=dp[i][t-v]+cost;							 dp[i][t]=max(last,max(dp[i][t],cur));						  }					 break;			case 1:				     for(int j=0;j<=T;j++)						 dp[i][j]=dp[i-1][j];				     for(int j=0;j
        
         =set[i].w[j].c;t--)						 {							 int v=set[i].w[j].c,cost=set[i].w[j].g;							 int last=dp[i-1][t-v]+cost;						//	 dp[i][t]=max(dp[i][t],max(dp[i-1][t],last));							 dp[i][t]=max(dp[i][t],last);//要么不选，要么从上一组的状态，在当前组选一个						 }				break;			case 2: 				     for(int j=0;j<=T;j++)						 dp[i][j]=dp[i-1][j];				     for(int j=0;j
         
          =set[i].w[j].c;t--)						 {							 int v=set[i].w[j].c,cost=set[i].w[j].g;							 int cur=dp[i][t-v]+cost;							 int last=dp[i-1][t-v]+cost;						//	 dp[i][t]=max(dp[i-1][t],max(dp[i][t],max(cur,last)));							 dp[i][t]=max(dp[i][t],max(last,cur));//比上一种情况多了一种选择， 就是可以从当前组继续多选择一个						 }				break;			}		}		if(dp[n][T]<0)			puts("-1");		else 		printf("%d\n",dp[n][T]);	}	return 0;}