题解

输入—>分装+状态标记（01、多重一种，完全一种）—>分别处理—>输出结果

#include<vector>
#include<iostream>
#include<algorithm>//一堆头文件
using namespace std;
struct obj{
    int w,v,type;
};//存储物品

vector<obj>a;//动态数组（直接用于DP）

void pack(int w,int v,int cnt){
    int t=1;
    while(cnt>0){
        int take=min(cnt,t);
        a.push_back({take*w,take*v,0});
        cnt-=take;
        t*=2;
    }
    return;
}//多重背包分装过程打包成函数
int main(){
    int M,N;
    cin>>M>>N;//输入
    
    for(int i=0;i<N;i++){
        int w,v,cnt;
        cin>>w>>v>>cnt;

        if(cnt==1){
            a.push_back({w,v,0});
        }else if(cnt>0){
            pack(w,v,cnt);
        }else{
            a.push_back({w,v,1});
        }
    }//不同种类的背包分类处理

    int dp[210]{};//DP数组

    for(int i=0;i<a.size();i++){
        int state=a[i].type,wi=a[i].w,vi=a[i].v;//取出数据方便处理
        if(state==1){
            for(int j=wi;j<=M;j++){
                dp[j]=max(dp[j],dp[j-wi]+vi);//完全背包正序处理
            }
        }else{
            for(int j=M;j>=wi;j--){
                dp[j]=max(dp[j],dp[j-wi]+vi);//01背包&多重背包逆序处理
            }
        }
    }
    cout<<dp[M];//输出
    return 0;
}