拟阵：贪心算法的理论基础
拟阵是满足下列条件的一个序队M = (S, I)
①S是一个有穷的集合，I是集合的集合且非空
②I具有遗传性质：如果集合B∈I 且 A
⊂
B，则A∈I，即若B∈I，则B是S的独立子集，且B的任意子集也都是S的独立子集，空集必为I的成员
③I满足交换性质：如果A∈I，B∈I且|A|<|B|，其中
|B|表示B集合的长度，那么一定存在元素x，满足x∈B且x∉A，使得A∪{x}属于I
根据③性质，可推出④M(S, I)对于I中的独立子集A，若x∈S但x∉A，且x加入A中仍可以保持独立性，那么称x为A的可扩展元素，
当A不能再扩展时，A就是一个极大独立子集，所有极大独立子集都具有相同的势（元素个数）
加权矩阵：S集合中所有的元素x都有一映射值F(x)>0，假设A
⊂S，那么F(A) = ∑F(x) (x∈A)
这样所有的贪心过程，都可以类比为在加权矩阵中找到一个拥有最大权值的独立子集的问题
过程如下：While(S不为空) { x = Getmax(S); if(A∪{x}∈I) A =
A∪{x}
证明贪心算法返回的是一个最优子集：
引理①：对于任意一个拟阵M =
(S, I)，如果x是独立子集A的一个可扩展元素，那么x也必然是空集的一个可扩展元素，
这个引理说明了如果一个元素x不能当时被用到，那么以后也永远不可能被用到
引理②：
对于任意一个加权拟阵M =
(S, I)，
若某个x使得W(x)最大，且{x}∈I，那么一定存在一个包含元素x的最优独立子集A，根据上面的性质④，可得选择x没有任何问题且一定要选
这样如果当前使F[x]最大的x已经加入集合，那么问题可以缩减为在新的加权矩阵M’ = (S’, I’)中找一个最大权值的独立子集问题，其中
S’ = {y∈S | {x,y}∈I}
I’ = {B⊂S-{x}|B∪{x}∈I}，
问题规模就被缩小但仍然符合性质和引理
∴贪心算法返回的一定是最优答案
举例：
Kruskal求解最小生成树
为什么是对的？
首先证明对于无向图G = (V, E)，定义S[G]是图G的边集E，M[G] = (S[G], I[G])，如果A是E的子集且A不构成回路，那么A属于I[G]，这样的
M[G]是拟阵
那就看M[G]满不满足性质
对于①：I[G]一定遗传，因为一个没有回路的森林去掉一条边之后更不可能出现环
对于②：具有m条边的森林包含|V|-m棵树，若A和B都是G的森林，且|B|>|A|，那么B中树的个数一定小于A中树的个数，那么必有边e(u, v)∈B，但∉A，使得将边e添加进A中仍然没有回路，即A∪{e}∈I
命题得证：M[G]是拟阵，当然每条边是有长度的，每条边e的长度就相当于F(e)，这样就构成一个加权矩阵
这也意味着就可以将边权从小到大排序然后以一条边一条边的判断能否加入图中（这个过程同等于对于每个x判断
x是否独立子集的一个可扩展元素，最后得出的最优独立级就等于最小生成树
）Kruskal是正确的！
3105: [cqoi2013]新Nim游戏
Time Limit:
10 Sec
Memory Limit:
128 MB
Submit:
1298
Solved:
758
[
Submit
][
Status
][
Discuss
]
Description
传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。
本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。
如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。
Input
第一行为整数
k
。即火柴堆数。第二行包含
k
个不超过10
9
的正整数，即各堆的火柴个数。
Output
输出第一回合拿的火柴数目的最小值。如果不能保证取胜，输出-1。
Sample Input
6
5 5 6 6 5 5
Sample Output
21
一般Nim游戏的必败条件是所有数异或为0，而一轮操作之后就变回正常的尼姆博弈了，
所以在你一第一次取完之后，剩下的石子堆一定不能存在异或为0的子集，
也就是说剩下的n个数一定要线性无关
将每个数拆成二进制形式的向量即可构成一个矩阵，即要求这个矩阵线性无关（异或）
首先很容易得出先手无论如何都必赢，因为这个线性无关矩阵一定存在（只要你第一回合取得只剩下一堆石子不就必赢了，只不过这样你取得石子就太多了）
那么如何找出这个所有值之和最大的线性无关矩阵呢？其实直接贪心就好了，因为这个火柴集合是个拟阵！，拟阵的说明在上面
问题主要就是如何确定是个拟阵？
令n个火柴构成的集合S，若A∈S，且A中所有子集异或都不为0，那么A∈I，证明M = (S, I)是个拟阵
遗传性：这个就不用证了
交换性：设A, B∈I，且|B|>|A|，首先可以确定的是集合A和集合B中所有的元素都一定不相同！假设B中所有的元素都可以通过A的子集来表示，即B中的所有元素都不能成为集合A的扩展，那么B中所有元素的异或值一定为0，这样B就一定∉I，所以B中一定有元素不能通过A的自己来表示，即存在x∈B，A
∪{x}∈I
证必
所以这题直接按石子数量大小排序，然后遍历一遍就好，具体怎么实现，代码中有解释
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
int a[105], c[45];
int main(void)
{
LL sum, ans;
int n, i, temp, j;
while(scanf("%d", &n)!=EOF)
{
sum = ans = 0;
for(i=1;i<=n;i++)
scanf("%d", &a[i]);
for(i=1;i<=n;i++)
sum += a[i];
sort(a+1, a+n+1);
memset(c, 0, sizeof(c));
for(i=n;i>=1;i--)
{
temp = a[i];
for(j=30;j>=0;j--)
{
if(a[i]&(1<<j))
{
if(c[j]==0) // 假设当前独立子集A中所有的元素第j位都为0，而a[i]第j位为1，
{ // 那么说明a[i]一定可以扩展到独立子集A中
c[j] = i;
break;
}
else
a[i] ^= a[c[j]]; // 假设当前独立子集A中存在元素x中最后一个第j位为1，而a[i]第j位也为1，
} // 那么首先要将a[i]异或a[x]使得第j位为0，然后继续判定，因为a[i]可能无法扩展
}
if(a[i]) //如果最后a[i]不为0，那么说明a[i]无论怎么和独立子集A中的集合异或一定都不会为0，a[i]一定可以扩展到独立子集A中
ans += temp;
}
printf("%lld\n", sum-ans);
}
return 0;
}