算法2

动态规划

多重背包的简单的应用
其实多重背包的就是01背包的一个拓展，对于每个物品
我们可以选，也可以不选，但不同的是对于每个物品，我们会有s个和它相同的，对于这s个相同的物品，我们可以将它们放到一起来看，就相当于于一个体积是sv,价值是vs的一个物品，
所以在第二维枚举体积的时候，我们也是从大到小进行的转移

有不对的地方，还请大佬多多指出

参考文献

acwing.com基础课

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int f[maxn];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=m;j>=v;j--)
        {
            for(int k=1;k<=s&&k*v<=j;k++)
                f[j]=max(f[j],f[j-k*v]+w*k);
        }
    }
    cout<<f[m]<<endl;
}