日期:2014-05-20  浏览次数:21087 次

求算法高手指点
问题: 一个人可以有三本证书:A 证 B 证 C 证 (可以有1~3本),现在有 10 个人,从中随机抽取 5 人,要求拥有 A 证 2 人,B 证 2 人,C 证 1人。用什么算法?

注: 1. 假如某个人拥有 A 证 B 证,抽取A证时抽到该人,抽取B 证不会再抽到该专家。

 

------解决方案--------------------
先用只有1本证书的人填充,假设这样以后A证书的人满了,那么就将有AB,AC证书的当B,C证书处理。继续填充,最后不够就用有3本证书的人。所以证书越多工作机会越少。。。
------解决方案--------------------
C# code

    static void Main(string[] args)
    {
        var allExperts = new List<Expert>() {
            new Expert{ name="专家1", certs=new[]{ "A", "B"} },
            new Expert{ name= "专家2", certs=new[]{"A","B" }},
            new Expert{ name= "专家3", certs=new[]{"A" }},
            new Expert{ name= "专家4", certs=new[]{"A","C" }},
            new Expert{ name= "专家5", certs=new[]{"A" }},
            new Expert{ name= "专家6", certs=new[]{"B" }},
            new Expert{ name= "专家7", certs=new[]{"A" }}, 
            new Expert{ name= "专家8", certs=new[]{"C" }}, 
            new Expert{ name= "专家9", certs=new[]{"C" }}, 
            new Expert{ name= "专家10", certs=new[]{"C" }} 
        };
        var groups = new List<Group>() { 
            new Group{cert="A", need = 2},
            new Group{cert="B", need = 2},
            new Group{cert="C", need = 1}
        };

        var rand = new Random();

        Func<List<Expert>, string, int, List<Expert>> draw = (experts, cert, count) =>
        {
            var picked = experts.Where(e => e.certs.Contains(cert)).OrderBy(e => rand.Next()).Take(count).ToList();
            experts.RemoveAll(e => picked.Contains(e));
            return picked;
        };

        Action<Group> pick = null;
        pick = group =>
        {
            group.experts.AddRange(draw(allExperts, group.cert, group.lacks));
            if (group.lacks > 0)
            {
                groups.Take(groups.IndexOf(group)).Reverse().ToList().ForEach(g =>
                {
                    group.experts.AddRange(draw(g.experts, group.cert, group.lacks));
                    pick(g);
                });
            }
        };

        foreach (var g in groups)
            pick(g);

        foreach (var g in groups)
                Console.WriteLine("{0}: {1}", g.cert, g.lacks > 0 ? "专家不够" : string.Join(", ", g.experts.Select(e => e.name)));
    }

    public class Expert
    {
        public string name;
        public string[] certs;
    }

    public class Group
    {
        public string cert;
        public int need;
        public List<Expert> experts = new List<Expert>();
        public int lacks
        {
            get { return need - experts.Count; }
        }
    }

------解决方案--------------------
Private Enum ExpertEnum
A = 1 'a证
B = 2 'b证
C = 4 'c证
D = 8 '选中状态
End Enum

Private Nerd(9) As Boolean

Private Function GetNerdID(ByVal nExpertEnum As ExpertEnum) As Integer '取得指定证书的专家ID并设置专家下次不可选
Dim i As Integer
For i = 0 To 9
If (Nerd(i) And ExpertEnum.D) = False Then
If Nerd(i) And nExpertEnum Then '位与运算
Nerd(i) = Nerd(i) Or ExpertEnum.D '位或运算
Return i
End If
End If
Next
End Function

Private Sub GetNerdID(ByVal nNerdID As Integer, ByVal nExpertEnum As ExpertEnum) '设置指定的专家有指定的证书 
Nerd(nNerdID) = Nerd(nNerdID) Or nExpertEnum '位或运算
End Sub

Private Sub Clear() '重新来过 
ReDim Nerd(9)