C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1010;
int f[N];

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

    //每个物品之间互相独立
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;

        if(s==0)//完全背包
        {
            for(int j=v;j<=m;j++)
                f[j]=max(f[j],f[j-v]+w);
        }
        else
        {
            if(s==-1) s=1;//相当于s为1的多重背包

            //多重背包
            int k=1;
            while(k<=s)
            {
                for(int j=m;j>=v*k;j--)
                    f[j]=max(f[j],f[j-v*k]+w*k);

                s-=k;
                k*=2;
            }

            if(s)
                for(int j=m;j>=v*s;j--)
                    f[j]=max(f[j],f[j-v*s]+w*s);
        }
    }

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