题意：

某人要买鞋，有k个品牌，每个品牌有j个款，每款都有标价和价值，要求已经M元内，每个品牌至少买一双鞋的最大价值和。

思路：

1. 要求每一组之中至少有一个被选中，和之前的最多有一个稍有区别，需要把题目再次细分。

2. dp[i][j] 表示选定 i 个品牌并且花费为 j 的最大价值，dp[i][j] 为正数表示状态存在，为负数表示状态不存在。

3. dp[i][j] = max(dp[i][j], dp[i][j - v_k] + w_k);      第 i 类品牌有选择并且要选择第 k 件物品。（不选择第 k 件物品是相等的，所以略过转移方程）

   dp[i][j] = max(dp[i][j], dp[i - 1][j - v_k] + w_k);  第 i 类品牌前面没有选择并且要选择第 k 件物品。

4. 由于状态是从 0 到 i 的且 dp[0][j] = 0，其他为 -INFS 。所以只有当第一类品牌的状态存在时，才能推导出来第二类品牌的存在状态，以此类推。

5. 题目中有 2 个陷阱，一是可能会存在某品牌数量为 0 的情况，另外会存在费用或价格为 0 的情况，所以状态转移方程不能调换。

 

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXD = 10010;const int MAXN = 12;const int INFS = 0x3fffffff;vector
       
        
          > brand[MAXN];int dp[MAXN][MAXD];int main(){    int n, m, k;    while (scanf("%d %d %d", &n, &m, &k) != EOF)    {        for (int i = 1; i <= k; ++i)            brand[i].clear();        for (int i = 0; i < n; ++i)        {            int id, w, v;            scanf("%d %d %d", &id, &w, &v);            brand[id].push_back(make_pair(w, v));        }        memset(dp[0], 0, sizeof(dp[0]));        int cflag = 0;        for (int i = 1; i <= k; ++i)        {            for (int v = 0; v <= m; ++v)                dp[i][v] = -INFS;            if (!brand[i].empty())                ++cflag;            for (int j = 0; j < brand[i].size(); ++j)            {                int w = brand[i][j].first;                int val = brand[i][j].second;                for (int v = m; v >= w; --v)                {                    dp[i][v] = max(dp[i][v], dp[i][v - w] + val);                    dp[i][v] = max(dp[i][v], dp[i - 1][v - w] + val);                }            }        }        if (cflag == k && dp[k][m] > 0)            printf("%d\n", dp[k][m]);        else            printf("Impossible\n");    }    return 0;}