Description：

有 $n$ 件装备，每件装备有 $m$ 个属性，每个装备需要花费 $c_i$ ，如果一件装备的属性能由其他购买的装备的属性线性组合出，则不用买，求买下最多数量的装备的情况下花的最少的钱。

$1\le n,m\le500$

Solution：

线性组合不难想到线性基，线性基的最大维数是固定的，所以线性基中的最大向量个数是确定的，也就是说原集合的极大独立集的大小是确定的，所以这个问题是一个拟阵上的最优化问题，因此可以将装备按花费排序，一个一个地加入，用实数下的线性基判断是否合法即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 510

struct equip

{

	double k[MAXN];

	int cost;

}t[MAXN];

bool cmp(equip a,equip b){return a.cost < b.cost;}

const double eps = 1e-5;

struct LinearBase

{

	int cost,cnt;

	equip p[MAXN];

	bool v[MAXN];

	LinearBase(){memset(v,false,sizeof(v));cost = cnt = 0;}

	void insert(equip g)

	{

		for(int i = 1;i <= m;++i)

		{

			if(fabs(g.k[i]) > eps)

			{

				if(v[i] == false)

				{

					p[i] = g;v[i] = true;

					++cnt;

					cost += g.cost;

					break;

				}

				else

				{

					double div = g.k[i] / p[i].k[i];

					for(int j = i;j <= m;++j)

					{

						g.k[j] -= p[i].k[j] * div;

					}

				}

			}

		}

	}

}LB;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			scanf("%lf",&t[i].k[j]);

		}

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&t[i].cost);

	}

	sort(t + 1,t + 1 + n,cmp);

	for(int i = 1;i <= n;++i)

	{

		LB.insert(t[i]);

	}

	cout << LB.cnt << " " << LB.cost << endl;

	return 0;

}