不过还是很难。
#include<stdio.h>
#define max(a,b) (a>b?a:b)
int main(){
int n,m,i,j,k;
int k1=0,k2=0;
int t1=0,t2=0;
int v[200]={0},p[200]={0},q[200]={0},dp[32005]={0};
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d %d %d",&v[i],&p[i],&q[i]);
}
for(i=1;i<=m;i++){
k1=0;
k2=0;
t1=0;
t2=0;
if(q[i]==0){
for(k=i+1;k<=m;k++){
if(q[k]==i){
t1=k;
k1=1;
break;
}
}
for(k=t1+1;k<=m;k++){
if(q[k]==i){
t2=k;
k2=1;
break;
}
}
for (j = n; j >= v[i]; j--){
dp[j] = max(dp[j - v[i]] + v[i] * p[i], dp[j]);
if (j-v[i]-v[t1]>=0 && k1==1) dp[j] = max(dp[j - v[i]-v[t1]] + v[i] * p[i]+v[t1]*p[t1],dp[j]);
if (j - v[i] - v[t2] >= 0 && k2 == 1) dp[j] = max(dp[j - v[i] - v[t2]] + v[i] * p[i] + v[t2] * p[t2], dp[j]);
if (j - v[i] - v[t1] - v[t2] >= 0 && k1 == 1 && k2 == 1) dp[j] = max(dp[j - v[i] - v[t1]-v[t2]] + v[i] * p[i] + v[t1] * p[t1] + v[t2] * p[t2], dp[j]);
}
}
}
printf("%d",dp[n]);
return 0;
}