(动态规划 - 分组背包问题)

题目描述
自从 01 背包问题被提出以来，小 A 对其产生了浓厚的兴趣。某日，小 A 前去旅行，却发现他的背包与传统的 01 背包存在差异。他的物品大致可以划分为 k 个组别，每个组内的物品之间存在互斥关系。此时，他希望确定在这些条件下所能获得的最大利用价值。

输入格式
给出两个数值 m 和 n，分别表示背包的总容量为 m，以及物品的总数为 n。

随后的 n 行中，每行包含三个数值 ai、bi、ci，分别代表该物品的重量、利用价值以及所属的组别编号。

输出格式
输出一个数值，表示在满足条件的情况下所能达到的最大利用价值。

输入输出样例
输入

    45 3
    10 10 1
    10 5 1
    50 400 2
    
    
      
      
      
      
    

    10
    
    
      
    

说明/提示：
m与n的取值范围限定在1至1000之间。
相关程序代码如下：

    #include <iostream>
    using namespace std;
    int max(int a,int b)
    {
    	return a>b?a:b;
    }
    int n,m,t,x;
    int