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

结论： $f[i][j]=\max\{ f[i-1][j-k\cdot v[i]]+k\cdot w[i]\}\ (0\leqslant k \leqslant s[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 = 6010;

int n,m;
int f[N];

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=m;j>=v;j--) //保证了 f[j - k * v] 是 f[i - 1][j - k * v]
            for(int k=0;k<=s&&k*v<=j;k++)
                f[j]=max(f[j],f[j-k*v]+k*w);
    }

    cout<<f[m]<<endl;

    return 0;
}