题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int f[1010];
struct Thing
{
    int kind;
    int w,c;
};
int main()
{
    int n,m;
    vector<Thing> things;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,c,s;
        cin>>v>>c>>s;
        if(s<=0)
            things.push_back({s,v,c}); //将01和完全背包直接加入新的物品
        else //将多重背包二进制优化以后加入新的物品
        {
            for(int t=1;t<=s;t=t*2)
            {
                s=s-t;
                things.push_back({-1,v*t,c*t});
            }
            if(s!=0) 
            {
                things.push_back({-1,v*s,c*s});
            }
        }

    }
    for(auto x:things) //依次遍历每个物品
    {
        if(x.kind<0) //01背包
        {
            for(int j=m;j>=x.w;j--)
            {
                f[j]=max(f[j],f[j-x.w]+x.c);
            }
        }else  //完全背包
        {
            for(int j=x.w;j<=m;j++)
            {
                f[j]=max(f[j],f[j-x.w]+x.c);
            }
        }
    }
    cout<<f[m];
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla