$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

结论： $f[i][j][k]=\max(f[i-1][j][k],f[i-1][j-v[i]][k-m[i]]+w[i])$

思路：

• $1. 状态表示$
  $集合：只从前\ i\ 个里面选，体积不能超过\ j，重量不能超过\ k\ 的价值$
  $属性：\max$

• $2. 状态转移$
  $不选第\ i\ 个物品：f[i-1][j][k]$
  $选择第\ i\ 个物品：f[i-1][j-v[i]][k-m[i]]+w[i]$

• $3. 滚动数组$
  $由于\ f[i][j][k]\ 只需用到当前层和上一层，则结论可转化为：$
  $f[j][k]=\max(f[j][k],\ f[j-v[i]][k-m[i]]+w[i])$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n,V,M;
int f[N][N]; //只从前 i 个物品里面选，体积不超过 j，重量不超过 k 的最大价值

int main()
{
    cin>>n>>V>>M;

    for(int i=0;i<n;i++)
    {
        int v,m,w;
        cin>>v>>m>>w;
        for(int j=V;j>=v;j--)
            for(int k=M;k>=m;k--)
                f[j][k]=max(f[j][k],f[j-v][k-m]+w);
    }

    cout<<f[V][M]<<endl; //只从前 n 个物品里面选，体积不超过 V，重量不超过 M 的最大价值

    return 0;
}