2 44 66

这题属于分组背包，但和多个取一个的不同，这里是至少取一个，可以设dp[i][j]表示前i组花费j元所能得到的最大价值，dp[i][j]先都初始化为-1，然后把dp[0][i]都记为0，在判断的时候要加上两个if，就是如果转移过来的状态是-1，那么这个状态已经不能成立了，所以当前这个状态肯定不能成立，这一点可以动笔画一下。

#include<stdio.h>

#include<string.h>

int max(int a,int b){

	return a>b?a:b;

}

int dp[13][10060],num[13];

struct node{

	int w,v;

}a[13][105];

int main()

{

	int n,m,i,j,k,lei,c,d,e;

	while(scanf("%d%d%d",&n,&m,&lei)!=EOF)

	{

		memset(a,0,sizeof(a));

		memset(num,0,sizeof(num));

		for(i=1;i<=n;i++){

			scanf("%d%d%d",&c,&d,&e);

			num[c]++;a[c][num[c]].w=d;a[c][num[c]].v=e;

		}

		memset(dp,-1,sizeof(dp));

		//for(i=0;i<=lei;i++)dp[i][0]=0;注意：这里不能把每一行的dp[i][0]记为0，因为这样前面一行未满足至少取1个的条件是-1的话，那么这行也应该是-1，不是0.

		for(i=0;i<=m;i++)dp[0][i]=0;

		for(i=1;i<=lei;i++){

			for(k=1;k<=num[i];k++){

				for(j=m;j>=a[i][k].w;j--){

					if(dp[i][j-a[i][k].w]!=-1)//这里两个if不能换顺序，因为第一个if是对这一组的多个背包进行挑选，

					dp[i][j]=max(dp[i][j],dp[i][j-a[i][k].w]+a[i][k].v);//如果先进行第二个if，那么可能当前的dp[i][j]不再为-1，

					if(dp[i-1][j-a[i][k].w]!=-1)//然后运行第一个if的时候可能会产生冲突，

					dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][k].w]+a[i][k].v);//即原来不能成立的状态变为可能然后再进行背包运算 。

				}

			}

		}

		if(dp[lei][m]<0)printf("Impossible\n");

	    else printf("%d\n",dp[lei][m]);

	}

	return 0;

}