代码：

include<bits/stdc++.h>

using namespace std; int N,M,VM[100]={0},WM[100]={0},dp[100][32001],VF[100][3]={{0}},WF[100][3]={{0}},belong[100]={0}; int main(){ cin>>N>>M; for(int i=1;i<=M;i++){ int a,b,c; cin>>a>>b>>c; if(c==0) VM[i]=a,WM[i]=ab; else{ belong[c]++; VF[c][belong[c]]=a; WF[c][belong[c]]=ab; } } memset(dp,0,sizeof(dp)); for(int i=1;i<=M;i++) for(int j=N;j>=VM[i];j--){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-VM[i]]+WM[i]); if(j-VM[i]-VF[i][1]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-VM[i]-VF[i][1]]+WM[i]+WF[i][1]); if(j-VM[i]-VF[i][2]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-VM[i]-VF[i][2]]+WM[i]+WF[i][2]); if(j-VM[i]-VF[i][1]-VF[i][2]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-VM[i]-VF[i][1]-VF[i][2]]+WM[i]+WF[i][1]+WF[i][2]); } cout<<dp[M][N]<<endl; return 0; }

4

4500 12 100 3 0 400 5 0 300 5 0 1400 2 0 500 2 0 800 2 4 1400 5 4 300 5 0 1400 3 8 500 2 0 1800 4 0 440 5 10