• 要点：
  (1)体积至多是j——f[i][j]全部置为0即可，要求j>=0
  (2)体积恰好是j——f[0][0]=0,要求j>=0其余的情况置为无穷即可（按照题目意思分析即可，求最大值的话——负无穷）之所以 这样的目的是丢弃掉原先的状态直接更新即可
  (3)体积至少是j——f[0][0]=0,这里不对体积做要求，因为恰好为一个负数的话，只需要将其重置为0即可，至少为负数，也可为至少是0，其余的与第二种情况一致
  分组背包的枚举方式：首先先枚举物品组数，然后枚举体积，最后枚举的是决策——可以是选几个也可以是按照体积来划分，需要做到每个方案都被枚举到

AcWing 1019. 庆功会
典型的多重背包模型，在这里不需要用优化，用朴素版即可

#include<iostream>

using namespace std;

const int N = 510,M= 6010;

int f[N][M];
int n,m;
int v[N],w[N],s[N];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> v[i] >> w[i] >> s[i];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=s[i]&&j>=k*v[i];k++)    
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

    cout << f[n][m] << endl;
    return 0;
}

AcWing 1020. 潜水员
这里的f[i][j][k]表示的是从前i组物品中选，氧气体积至少是j,氮气的体积至少是k的最小重量
和之前的分析一致：第i件物品选或者不选—— f[i-1][j][k],f[i-1][j-v[i]][k-s[i]]
（可以利用01背包的优化来将其优化掉一维）

举一个例子f[3][4]体积至少是3，价值至少是4，现只有一个物品v[i]=4,w[i]=4;
按照我们集合划分的定义来看，是符合题意的并且可以装入,f[3-v[i]][j-w[i]]此时发现第一维已经越界了，而我们发现
f[0][j-w[i]]也是符合题目意思的因此我们可以在这里将其判断一下，看是否会越界

#include<iostream>
#include<cstring>

using namespace std;

const int N = 30, M = 80;

int n,m;
int f[N][M];

int main()
{
    cin >> n >> m;
    int T;
    cin >> T;
    memset(f,0x3f,sizeof f);
    f[0][0]=0;

    for(int i=0;i<T;i++)
    {
        int v,w,s;
        cin >> v >> w >> s;
        for(int j=n;j>=0;j--)
            for(int t=m;t>=0;t--)//这样范围
                f[j][t]=min(f[j][t],f[max(j-v,0)][max(t-w,0)]+s);
    }
    cout << f[n][m] << endl;
    return 0;
}

AcWing 10. 有依赖的背包问题
与金明的预算方案那个题目类似只不过这个题目中的配件中的数目过多，如果用二进制枚举的话一定会超时，因此在这里我们采用枚举体积的方法，f[u][m]表示的是以u这个为根节点体积不超过m的最大价值。
首先建树，我们采用邻接表的方式，由于存在依赖关系，所以建一条单项边，首先先从根节点递归处理到叶子节点，从下向上依次求解（动态规划由于是一种暴力的优化，所以到最后可以求出正确答案）

#include<iostream>
#include<cstring>

using namespace std;

const int N = 110;

int f[N][N];
int v[N],w[N];
int n,m;
int h[N],e[N],ne[N],idx;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int son=e[i];
        dfs(son);
        //类似于分组背包
        for(int j=m-v[u];j>=0;j--)//由于必须要选择u这个父节点，所以在这里我们用通常处理的方式先去掉父节点，再加上去
            for(int k=0;k<=j;k++)
                f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
    }
    //将u这个点加入答案中
    for(int i=m;i>=v[u];i--)f[u][i]=f[u][i-v[u]]+w[u];
    //所有不能装下u这个点的子树的所有价值均为0，不能去掉，因为在上层的循环中可能会被赋值，因此需要将其覆盖为0
    for(int i=0;i<v[u];i++)f[u][i]=0;
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);

    int root;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin >> v[i] >> w[i] >> p;
        if(p==-1)root=i;
        else add(p,i);
    }

    dfs(root);
    cout << f[root][m] << endl;
    return 0;
}