解释一下蓝书上的做法
按照数学归纳法证明这个贪心，假设当前在第\(i\)行，前面已经选出\(i-1\)个线性无关的向量了（非零行），那么对于这一行，如果最终的结果不选\(z[k]\)，而是选了另一个\(z[l]\)，那么最终的向量组加入\(z[k]\)后就线性相关了，\(z[k]\)可以被这个向量组唯一表示；如果这个向量组去除了\(z[l]\)，那么剩下的向量还是线性无关的，如果加入\(z[k]\)变成了线性相关，那么\(z[k]\)也可以被这个向量组唯一表示，而且这种表示方法不含\(z[l]\)，也就是说前面那种表示方法也不含\(z[l]\)（因为表示方法唯一）；然而对行向量组进行初等行变换，每一个时刻任何一个行向量\(α\)都可以看做最开始的所有行向量的线性组合（而且\(α\)的系数一定不为\(0\)），而我们选取了\(z[l]\)后，会对\(z[k]\)进行消元，所以\(z[k]\)的线性表示包含\(z[l]\)，矛盾，也就是说删除\(z[l]\)加入\(z[k]\)的向量组仍然线性无关，是一个花费更低的极大无关组
然后讲一下我的做法，不按照行向量考虑而是按照列向量考虑，将所有的\(z\)全部变成列向量然后进行初等行变换
我们先不管\(z\)的顺序，直接进行初等行变换，最后化出来一个行简化梯形矩阵，很显然的一个极大无关组就是每个非零行的第一个非零元所在的列（也就是非自由元所在的列）
于是一个很自然的想法就是我们先将所有\(z\)按照花费从小到大排序，然后进行初等行变换，最后按照上述的方法选择就是最优的方案
证明：最终的向量组一定包含花费最低的向量，否则的话花费最低的向量可以被极大无关组表出，而且系数不全为\(0\)，于是极大无关组的某个向量就可以被替换为这个花费最低的向量；然后利用数学归纳法，假设我们现在的行简化梯形矩阵长成这个样子
现在在考虑第\(j\)列
如果第\(j\)列元素全为\(0\)了（指梯形下面的元素），那么这个列向量肯定不选，因为已经可以被前面选择的向量表出了（注意初等行变换不改变列向量之间的线性关系）；否则的话，这个向量一定要选，可以利用上面类似的反证法证明
标签：花费,装备,变换,无关,行向量,购买,初等,向量 From： https://www.cnblogs.com/dingxingdi/p/18170112