传送门：点击打开链接

题目大意：给你n件物品，每件有自己的品牌号，价格以及价值，问在每种品牌至少选一件的情况下，如何选能使价值最大？

解题思路：一开始以为是分组背包的模板题，没注意和《背包九讲》的情况有出入，《背包九讲》中要求是每组最多选1件，而这里则是至少选一件。一开始的思路是想在dp中先给他预处理每组价格最小的进去，然后删掉那件，但是这样感觉把问题变复杂了，第一，你要去处理那个包；第二，你还要思考以后如何更新这个包，怎么把之前的给替换掉或者增加。于是放弃了，今天重新搜了下题解，稍微理解了大牛们的方法，状态:dp[k][m]:表示用m元选k组鞋能够达到的最大价值。状态转移方程就挺有深度了，为什么这样讲？你一个包每次要去探索一个组的时候你要考虑这个组是否有放过，有的话你要考虑要不要选第二双或者是换一双，没放过的话就看看要拿哪双。单独考虑没放过的情况，即这组是没处理过的，这样的状态你要从前一组处理好的状态转移过来，即：dp[k][m]=dp[k-1][m-cost]；有处理的话，就是从本次这组的状态转移过来了,即：dp[k][m]=dp[k][m-cost]；至于要一双，两双，三双......那就是内层中01背包的事情了，于是我们得到这样一个状态转移方程:dp[k][m]=max(dp[k][m],dp[k-1][m-cost],dp[k][m-cost]),当然dp数组的初始化也很有灵性！dp<0时表示没处理过，dp[0][0...m]=0，表示0组的时候所有的价值都是0，这点很重要，因为选1组的状态肯定是通过选0组的状态得过来的！（ps：大佬们的思路实在牛逼，什么时候才能向他们一样呢？点击打开链接.这个博客思路挺好的。

AC代码如下：

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;

struct node
{
	int cost[110],value[110],size;
}pag[11];

int dp[11][100010],n,m,k;

int max(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int i,j,t,a,b,c,z;
	while(cin>>n>>m>>k)
	{
		memset(pag,0,sizeof(pag));
		for(i=1;i<=n;i++)
		{
			cin>>a>>b>>c;
			pag[a].cost[pag[a].size]=b;
			pag[a].value[pag[a].size]=c;
			pag[a].size++;
		}
		for(i=1;i<=k;i++)
			if(pag[i].size==0)
				break;
		if(i<=k)  //保证没组至少有一个
		{
			cout<<"Impossible"<<endl;
			continue;
		}
		memset(dp,-1,sizeof(dp));
		for(i=0;i<=m;i++) //注意边界条件  即一组都没选的话价值为0  所有状态都是从一组都没选出发
			dp[0][i]=0;
		for(i=1;i<=k;i++)
		{
			for(j=0;j<pag[i].size;j++)
				for(z=m;z>=pag[i].cost[j];z--)
				{
					dp[i][z]=max(dp[i][z],max(dp[i][z-pag[i].cost[j]]+pag[i].value[j],dp[i-1][z-pag[i].cost[j]]+pag[i].value[j]));
				}
		}
		if(dp[k][m]==-1)
			cout<<"Impossible"<<endl;
		else
			cout<<dp[k][m]<<endl;
	}
	return 0;
}