计算不匹配的袜子组合总数

Question

这是2015年ICPC NorthWest编程大赛的问题之一，我想知道有没有更简单或更有效的方法。

以下是问题所在：

“弗雷德喜欢穿不匹配的袜子。这有时意味着他必须提前计划。假设他的袜子抽屉里有一只红色，一只蓝色和两只绿色的袜子。如果他穿红色和蓝色的袜子，他就坚持穿绿色的袜子。如果他把红色和绿色配对，然后蓝色和绿色配对，他会把两双不匹配的袜子放在一起。考虑到他袜子抽屉里的东西，他可以放多少双不匹配的袜子？”

下面是一个示例输入：

Color 1 -> 4 socks

Color 2 -> 3 socks

Color 3 -> 7 socks

Color 4 -> 11 socks

Color 5 -> 4 socks

我这样做的方式是，我首先将输入读入一个数组，并对其进行递增排序。这样的话，我将在数组的末尾拥有最大数量的袜子。从这里开始，我基本上比较了arr[i]和arr[i-1]，并得到了它们之间的最小值。将其与总数相加，保存剩余部分，然后在数组中重复此过程。例如，使用示例输入，它看起来如下所示：

排序数组：[3,4,4,7,11]

1:3 socks ---> 1:3 socks ---> 1:0 socks ---> 1:0 socks

2:4 socks ---> 2:4 socks ---> 2:1 socks ---> 2:1 socks

3:4 socks ---> 3:4 socks ---> 3:0 socks ---> 3:0 socks

4:7 socks ---> 4:0 socks ---> 4:0 socks ---> 4:0 socks

5:11 socks ---> 5:4 socks ---> 5:0 socks ---> 5:0 socks

------>总数= 14种可能的不匹配袜子组合。这似乎是一种过于天真的方法。有没有人有关于如何优化它的想法？如果需要的话，我可以发布我的代码。

Answer 1

我认为最优的解决方案可以通过检查所有可能的不同袜子颜色的分组到2堆中找到。对于每个这样的分组，可以产生奇数对袜子，其中p是最小堆中的袜子的数量。您需要提供最大p的分组。您可以递归地将所有可能的袜子分组生成2堆。

下面是一些用于说明的Java代码：

public static void main(String[] args)
{
    int[] socks = {3,4,4,7,11};
    System.out.println(count(0, 0, socks, 0));
}

static int count(int a, int b, int[] socks, int i)
{
    if(i == socks.length)
    {
        return Math.min(a, b);
    }

    return Math.max(count(a+socks[i], b,          socks, i+1), 
                    count(a,          b+socks[i], socks, i+1));
}

输出：

14

Answer 2

“希望这次能改正！”方法

第一步:检查是否还有2种或更多的颜色。如果没有或只剩下一种颜色，你就完成了(找不到更多的颜色)。

步骤2:找出一个非零计数最小的颜色

步骤3:排除计数最低的颜色(如果所有颜色都有相同的计数)；找出计数最高的颜色，并确定有多少颜色具有最高计数

步骤4:排除计数最低的颜色和计数最高的所有颜色；尝试找到第二大计数。

步骤5a:如果存在第二高计数，则计算amount_to_pair = min(highest_count - second_highest_count, lowest_count)。

步骤5b:如果没有第二高的计数，则计算amount_to_pair = lowest_count。

步骤6:通过将具有最低数量的袜子与具有最高数量的颜色的袜子尽可能均匀地配对来创建amount_to_pair对(例如，如果有9只红色袜子，20只蓝色袜子和20只绿色袜子；然后创建5对“红色和蓝色”以及4对“红色和绿色”)。

步骤7:转到步骤1。

示例(评论中提到的病理案例)：

初始条件

Color 1 -> 1 socks
Color 2 -> 20 socks
Color 3 -> 80 socks
Color 4 -> 81 socks

第一次迭代：

Color 1 -> 1 socks (lowest non-zero count)
Color 2 -> 20 socks
Color 3 -> 80 socks (2nd highest count)
Color 4 -> 81 socks (highest count)

Amount to remove = min(81-80, 1) = 1

Color 1 -> 1-1=0 socks (lowest non-zero count)
Color 2 -> 20 socks
Color 3 -> 80 socks
Color 4 -> 81-1=80 socks (highest count)

Results so far:
   (1 pair of colour 1 and colour 4)

第二次迭代：

Color 1 -> 0 socks
Color 2 -> 20 socks (lowest non-zero count)
Color 3 -> 80 socks (highest count)
Color 4 -> 80 socks (highest count)

Amount to remove = 20

Color 1 -> 0 socks
Color 2 -> 20-20=0 socks (lowest non-zero count)
Color 3 -> 80-(20/2)=70 socks (highest count)
Color 4 -> 80-(20-20/2)=70 socks (highest count)

Results so far:
   (1 of colour 1 and colour 4)
   (10 of colour 2 and colour 3)
   (10 of colour 2 and colour 4)

第三次迭代：

Color 1 -> 0 socks
Color 2 -> 0 socks
Color 3 -> 70 socks (lowest non-zero count)
Color 4 -> 70 socks (highest count)

Amount to remove = 70

Color 1 -> 0 socks
Color 2 -> 0 socks
Color 3 -> 70-70=0 socks (lowest non-zero count)
Color 4 -> 70-70=0 socks (highest count)

Results so far:
   (1 of colour 1 and colour 4)
   (10 of colour 2 and colour 3)
   (10 of colour 2 and colour 4)
   (70 of colour 3 and colour 4)

原始方法

警告:下面的方法在各种病理情况下都会给出错误的结果(已经被上面的算法更新/替换)。我留在这里是为了给的一些评论提供上下文

起始条件：

Color 1 -> 4 socks
Color 2 -> 3 socks
Color 3 -> 7 socks
Color 4 -> 11 socks
Color 5 -> 4 socks

找到最高计数和最低计数；并删除计数最低的，这样它就不存在了：

Color 1 -> 4 socks
Color 3 -> 7 socks
Color 4 -> 11-3=8 socks
Color 5 -> 4 socks

Results so far:
   (3 of colour 2 and colour 4)

再做一次：

Color 3 -> 7 socks
Color 4 -> 8-4=4 socks
Color 5 -> 4 socks

Results so far:
   (3 of colour 2 and colour 4)
   (4 of colour 1 and colour 4)

再做一次：

Color 3 -> 7-4=3 socks
Color 5 -> 4 socks

Results so far:
   (3 of colour 2 and colour 4)
   (4 of colour 1 and colour 4)
   (4 of colour 4 and colour 3)

再做一次：

Color 5 -> 4-3=1 sock

Results so far:
   (3 of colour 2 and colour 4)
   (4 of colour 1 and colour 4)
   (4 of colour 4 and colour 3)
   (4 of colour 3 and colour 5)

停下来，因为只剩下一种颜色了。

Answer 3

构建图形数据结构。每只袜子都是顶点。创建从每个顶点到另一种颜色的所有顶点的边。

现在找到maximum matching的幂-没有公共顶点的边集的大小。

您可以使用Edmonds algorithm在O(V^2*E)的多项式时间内构建最大匹配。似乎这个任务的图是密集的，所以复杂度趋向于O(V^4)。也存在复杂度较低的Micali和Vazirani算法(不知道实现难度)。

如果您的任务不需要最大匹配本身-只有边数，那么可以使用基于Tutte矩阵定理的随机化Lovasz算法来计算该值。(我没有找到简明的英文描述-也许术语可能不同，俄语中的简短描述是here)