题面描述
在抽屉里有20只手套。其中，5双黑手套，3双棕色手套和2双灰手套。你只能在黑暗中挑手套，并且只能将手套挑出之后才能检查颜色。最少要挑多少次才能满足以下条件
a> 至少挑出一双颜色匹配的手套
b> 所有颜色的手套都至少挑出一双匹配的。
分析
总计有5 * 5 * 3 * 3 * 2 * 2 =900种状态，单向图，每个顶点最多会与6个其他顶点相连。遍历图可以找到所有解，取最长路径。
但是否一定要这样穷举呢， 如果是由人类来计算，在反向最优的选择下可以将问题的描述转换为以下形式，然后在其结果的基础上+ 1。
在满足以下条件的前提下，最多可以挑多少次：
a> 不能挑出任何一双颜色匹配的手套。 20 / 2 + 1 = 11
b> 至少有一种颜色的手套凑不齐一双。 20 - 2 + 1 = 19
实现
每一次都遍历6种选择，找一个满足条件的挑选方式，直到不能再挑为止。
class Program
{static void Main(string[] args){//a:var count = Function((state) => !(state.HasBlackPair() || state.HasBlownPair() || state.HasGreyPair()));Console.WriteLine($"最少要挑{count}次才能至少挑出一双颜色匹配的手套");//b:var a = Function((state) => !state.HasBlackPair());var b = Function((state) => !state.HasBlownPair());var c = Function((state) => !state.HasGreyPair());Console.WriteLine($"最少要挑{Math.Max(Math.Max(a,b),c)}次才能所有颜色的手套都至少挑出一双匹配的");Console.ReadKey();}private static int Function(Func<State, bool> predicate){int sum = 0;var state = new State();while (true){if (state.TryAddOne(predicate)){sum++;}else{break;}}return sum + 1;}
}public class State
{private int[] Data = new int[6];private int[] Max = new int[] { 5, 5, 3, 3, 2, 2 };public bool TryAddOne(Func<State,bool> predicate){for (int i = 0; i < 6; i++){if(Data[i] < Max[i]){Data[i]++;if (predicate(this)){return true;}else{Data[i]--;}}}return false;}public bool HasBlackPair(){return Data[0] > 0 && Data[1] > 0;}public bool HasBlownPair(){return Data[2] > 0 && Data[3] > 0;}public bool HasGreyPair(){return Data[4] > 0 && Data[5] > 0;}
}
