舞蹈对算法（男性可以与一个或多个女性共舞） [英] Dance pair algorithm (Male may dance with one or more women )

问题描述

我有一个问题：-
有m个男人和m个女人。男性可以与一个或多个女人共舞，也可以不与任何一个共舞。找到一对一对舞伴，例如：
1.男性舞伴与自己选择的女性配对
2.没有一个男性或女性舞者独处

I have a problem:- There are m men and m women. Male may dance with one or more women or may not dance with any. Find One to one dancing partner pairs such that: 1. male dance partner is paired with women of his choice 2. No male or female dancer is left alone

public class DancePair 
{ 

    public static int totalmatching(int input1,String[] input2)
    {
        //Write code here
        String[] words=new String[input1];
        String[] words2=new String[input1];
        int i,j;
        System.out.println(input1);

        for(i=0;i<input1;i++)
        {
            words=input2[i].split("\\#");
            for(j=1;j<words.length;j++)
            {
                for(k=i+1;k<input1;k++)
                {
                    words2=input2[k].split("\\#");
                    for(p=1;p<words2.length;p++)
                    {
                        if(words[j]==words2.[p])
                        {
                            p++;
                            continue;
                        }
                        else
                        {
                            words3=input2[k+1].split("\\#");

                        }
                    }
                }

            }

        }
        return 0;
    }
}

输入类似：-M1＃W2＃W4， M2＃W1＃W2，M3＃W1＃W3＃W4，M4＃W4＃W5，M5＃W4
此i / p的输出应该为1
我已经创建了此代码，但我卡住了在循环中，无法继续。需要帮助

Input is like:- M1#W2#W4,M2#W1#W2,M3#W1#W3#W4,M4#W4#W5,M5#W4 OUTPUT should come for this i/p as 1 I have created this code but i am stucking in the loop and unable to proceed. Need help

推荐答案

此问题是最大匹配次数。您需要在此二部图中找到最大匹配项。唯一的区别是男人可以与多个女人跳舞。因此，当您构建图形时，对于每个人，您都需要针对其程度放置多个节点。考虑下面的示例：

This problem is a variation Maximum Matching. You need to find the maximum matching in this bipartite graph. The only difference is a man can dance with multiple women. So when you construct your graph, for each man you put multiple nodes with respect to its degree. Consider the following example:

M1: W1, W2
M2: W3

您必须为 M1 放置2个节点：

You have to put 2 nodes for M1:

M1: W1, W2
M1': W1, W2
M2: W3

现在您可以在此图中运行最大匹配，它将为您提供所需的结果。

Now you can run maximum matching on this graph, and it will give you the desired result.

这篇关于舞蹈对算法（男性可以与一个或多个女性共舞）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！