I love sneakers! （分组背包变形 每组至少买一个）

题目大意：

一个人去买鞋，有k种牌子，每种牌子至少买一双鞋子。每双鞋子有标价跟实际价值。求用m多的钱买最多价值的鞋。

n： 物品总数 ，m： 钱数， K： 牌子数  ，描述 s：牌号 ， v：标价， w：价值

解法：

首先看到题目很容易感觉得到这像是一个分组背包，但是又有点不一样。因为分组背包我们对于每组的物品最多选一件

所以我们的循环是这样的：

但是现在是每组至少选一个

仔细想一下，其实我们只需要把内层循环的顺序换一下就好了，因为我可以在之前选了的基础上再继续选

设dp[k][v]  表示选前k组物品我用钱数为v 的情况下能取到的最大价值总和。

那么我转移要么从前 k - 1 组转移  ，要么就是在当前 k 组选了基础上再继续选

特别注意一下：

这里必须把dp初始化为-1，或者-INF，dp[k][v] = -1 OR -INF 这是表示前k组用钱数为v还不能取到任何鞋。

memset(dp, -1, sizeof(dp));
没有一组的时候，无论你有多少money，当然此时的最大价值为0了
for(int v = 0; v <= M; v++) dp[0][v] = 0;   //或者memset(dp[0],0,sizeof(dp[0]);

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <math.h>
#include <cstdio>
#include <iomanip>
#include <time.h>

#define LL long long
#define INF 0x3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1

using namespace std;

const int maxn = 1e5 + 10;

struct Node {
    int v,w;
};

vector<Node> vec[15];
int dp[15][10010];

int main() {
    int n,m,k;
    while (~scanf("%d%d%d",&n,&m,&k)) {
        for (int i = 0;i < 15;i++) {
            vec[i].clear();
            for (int j = 0;j <= m;j++)
                dp[i][j] = -INF;
        }
        for (int i = 0;i <= m;i++)
            dp[0][i] = 0;
        for (int i = 1;i <= n;i++) {
            int c,v,w;
            scanf("%d%d%d",&c,&v,&w);
            vec[c].push_back({v,w});
        }
        for (int i = 1;i <= k;i++) {
            for (int s = 0;s < vec[i].size();s++) {
                for (int j = m;j >= vec[i][s].v;j--) {
                    dp[i][j] = max(dp[i][j],max(dp[i-1][j-vec[i][s].v],dp[i][j-vec[i][s].v])+vec[i][s].w);
                }
            }
        }
        if (dp[k][m] < 0)
            printf("Impossible
");
        else
            printf("%d
",dp[k][m]);
    }
    return 0;
}