$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

结论： $f[i][j]=\max\{ f[i-1][j-k\cdot v[i]]+k\cdot w[i]\}$

思路：

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

• $2. 状态转移$
  $第\ i\ 个物品选\ k\ 个（不超过体积的情况下）：f[i-1][j-k\cdot v[i]]+k\cdot w[i] \ (0\leqslant k \leqslant s[i])$

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

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n,m;
int v[N],w[N],s[N];
int f[N][N]; // 只从前 i 个物品里面选，体积不超过 j 的最大价值

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=1;j<=m;j++)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++) //第 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;
}