线性基优化购买策略 题解

问题分析

我们需要从 $n$ 个 $m$ 维向量中选择一个极大线性无关组，使得在装备数量最多的前提下总花费最小。

算法思路

1. 问题转化

将每个装备看作一个 $m$ 维向量 $\mathbf{z_i}$，问题转化为： 找到向量组的秩（最多装备数量） 在所有基中找出总价格最小的那一组

2. 贪心策略

使用贪心线性基算法： 将装备按价格从小到大排序 依次尝试将每个装备插入线性基 如果当前装备与基线性无关，直接加入 如果线性相关，用当前装备替换基中价格更高的装备

3. 高斯消元实现

代码中使用高斯消元法维护线性基：

struct PT {
    long double x[1005], y;  // x: 属性向量, y: 价格
} p[1005], xxj[1005];  // p: 所有装备, xxj: 线性基

bool Xxj(int k) {
    for (int i = 1; i <= m; i++) {
        if (-esp > p[k].x[i] || p[k].x[i] > esp) {  // 找到第一个非零分量
            if (!xxj[i].x[i]) {  // 该维度还没有基向量
                xxj[i] = p[k];
                return true;
            } else {
                // 消去当前向量的第i维
                long double z = p[k].x[i] / xxj[i].x[i];
                for (int j = i; j <= m; j++)
                    p[k].x[j] -= xxj[i].x[j] * z;
            }
        }
    }
    return false;
}

代码解析

数据结构

struct PT {
    long double x[1005], y;  // 属性向量和价格
};

主算法流程

1. 输入处理：

   for (int i = 1; i <= n; i++)
       for (int j = 1; j <= m; j++)
           cin >> p[i].x[j];  // 读入属性
   for (int i = 1; i <= n; i++)
       cin >> p[i].y;  // 读入价格
   

2. 价格排序：

   sort(p + 1, p + n + 1, cmp);  // 按价格升序排列
   

3. 构建线性基：

   for (int i = 1; i <= n; i++)
       if (Xxj(i))  // 成功插入线性基
           ans += p[i].y, ++cnt;  // 累加价格和装备数量
   

算法正确性证明

1. 装备数量最大化

由于我们总是尝试插入每个装备到线性基中，最终得到的基的大小等于向量组的秩，即最大可能的装备数量。

2. 花费最小化

按价格升序处理装备，当遇到线性相关的装备时： 如果新装备价格更低，会通过消元过程替换掉价格更高的基向量 这样就保证了在保持基的前提下最小化总花费

复杂度分析

排序：$O(n \log n)$ 高斯消元：$O(nm^2)$ 每个装备最多消元 $m$ 次 每次消元需要 $O(m)$ 时间 总复杂度：$O(nm^2)$，在 $n,m \leq 500$ 时可行

样例验证

输入：

3 3
1 2 3
3 4 5
2 3 4
1 1 2

处理过程： 1.按价格排序：装备1(1), 装备2(1), 装备3(2) 2.插入装备1：成功，基 = {装备1} 3.插入装备2：与装备1线性无关，成功，基 = {装备1, 装备2} 4.插入装备3：与装备1,装备2线性相关，跳过

结果：装备数量 = 2，总花费 = 1 + 1 = 2

数值稳定性

代码使用 long double 和误差范围 esp = 0.001 来处理浮点数精度问题，确保在实数域上的线性相关性判断正确。

总结

本题通过贪心线性基算法，结合价格排序和高斯消元，高效地解决了在保持线性无关的前提下最小化总花费的问题。算法保证了装备数量最大化（等于向量组的秩），并且在所有基中找到了价格和最小的那一个。