C :

#include <stdio.h>
int main(){
    int n, m;
    int dp[32001];  //dp[i]表示i元钱能够获得的最大重要度
    int lst[60][3];  //存放每个物品的主件和附件
    int imp[60][3];  //存放对应lst中物品的重要度
    for(int i=0; i<60; i++){  //初始化
        for(int j=0; j<3; j++){
            lst[i][j]=0;
            imp[i][j]=0;
        }
    }
    for(int i=0; i<=32000; i++) dp[i]=0;
    scanf("%d %d", &n, &m);  //读取总钱数和希望购买的物品个数
    for(int i=1; i<=m; i++){
        int v, p, q;
        scanf("%d %d %d", &v, &p, &q);
        if(q==0){  //物品是主件
            lst[i][0]=v;
            imp[i][0]=p;
        }else{  //物品时附件
            if(lst[q][1]==0){  //第一附件
                lst[q][1]=v;
                imp[q][1]=p;
            }else{  //第二附件
                lst[q][2]=v;
                imp[q][2]=p;
            }
        }
    }
    for(int i=1; i<=m; i++){  //动态规划
        if(lst[i][0]>0){
            for(int j=n; j>=0; j--){
                if(j>=lst[i][0]){  //只买主件
                    if(dp[j]<dp[j-lst[i][0]]+lst[i][0]*imp[i][0])
                        dp[j] = dp[j-lst[i][0]]+lst[i][0]*imp[i][0];
                }else{
                    break;
                }
                if(lst[i][1]>0 && j>=lst[i][0]+lst[i][1]){  //买主件和附件一
                    if(dp[j]<dp[j-lst[i][0]-lst[i][1]]+lst[i][0]*imp[i][0]+lst[i][1]*imp[i][1])
                        dp[j] = dp[j-lst[i][0]-lst[i][1]]+lst[i][0]*imp[i][0]+lst[i][1]*imp[i][1];
                }
                if(lst[i][2]>0){
                    if(j>=lst[i][0]+lst[i][2]){  //买主件和附件二
                        if(dp[j]<dp[j-lst[i][0]-lst[i][2]]+lst[i][0]*imp[i][0]+lst[i][2]*imp[i][2])
                            dp[j] = dp[j-lst[i][0]-lst[i][2]]+lst[i][0]*imp[i][0]+lst[i][2]*imp[i][2];
                    }
                    if(j>=lst[i][0]+lst[i][2]+lst[i][1]){  //买主件和附件一、二
                        if(dp[j]<dp[j-lst[i][0]-lst[i][1]-lst[i][2]]+
                        lst[i][0]*imp[i][0]+lst[i][1]*imp[i][1]+lst[i][2]*imp[i][2]){
                            dp[j] = dp[j-lst[i][0]-lst[i][1]-lst[i][2]]+
                            lst[i][0]*imp[i][0]+lst[i][1]*imp[i][1]+lst[i][2]*imp[i][2];
                        }
                    }
                }
            }
        }
    }
    printf("%d", dp[n]);  //输出n元钱获得的最大重要度
    return 0;
}
 

C++ :

#include<bits/stdc++.h>
using namespace std;

/*
  zw:主件价格,zv:主件价格*重要度
  fw:主件对应附件价格(第1列是个数，第23列是第几个附件)
  fv:附件价格*重要度
  dp：滚动存储每种情况下每个单位价格下的最大结果 
  n:总价格,m:总个数 
*/

int m,total;//m:件数,total:总金额 
int zw[40000],zv[40000];//主件金额，主件价值(金额*重要度) 
int fw[40000][4],fv[40000][3];//附件金额，附件价值 
int dp[40000],v,p,q;//dp:存储在i件物品的背包容量为j的情况下的最大价值 
int main(){
	int i,j;
	cin>>total>>m;
	//循环m件物品 
	for(i = 1;i <= m;i++){
		cin>>v>>p>>q;
		//如果是主件 
		if(q == 0){
			zw[i] = v;//价格 
			zv[i] = v * p;//价值度（价格*重要） 
		}else{
			//第q个物品的附件个数 
			fw[q][0]++;
			fw[q][fw[q][0]]=v;//第几个主件的价格
			fv[q][fw[q][0]]=v*p;//附件价值(价格*重要) 
		} 
	}
	
	//循环m个物品
	for(i = 1;i <= m;i++){
		//按背包的逻辑循环从总价格开始循环到每个主件的价格 
		for(j = total;j >= zw[i];j--){
			//在能装下这个物品的情况下，讨论：只要主件，主件+附件1，主件+附件2，主件+附件12
			//情况1：只要主件
			dp[j] = max(dp[j],dp[j-zw[i]]+zv[i]);
			//情况2：主件+附件1
			if(j>=zw[i]+fw[i][1]) dp[j]=max(dp[j],dp[j-zw[i]-fw[i][1]]+zv[i]+fv[i][1]);
			//情况3：主件+附件2
			if(j>=zw[i]+fw[i][2]) dp[j]=max(dp[j],dp[j-zw[i]-fw[i][2]]+zv[i]+fv[i][2]);
			//情况4：主件+附件12
			if(j>=zw[i]+fw[i][1]+fw[i][2]) 
			 dp[j]=max(dp[j],dp[j-zw[i]-fw[i][1]-fw[i][2]]+zv[i]+fv[i][1]+fv[i][2]);
		}
	} 
	cout<<dp[total];
	return 0;
}