algorithm - 计算不匹配的 socks 组合总数

这是2015年ICPC西北节目大赛的问题之一，我想知道是否有更简单或更有效的方法来做到这一点。
问题是：
“弗雷德喜欢穿不相配的袜子。这有时意味着他必须提前计划。
假设他的袜子抽屉里有一只红袜子、一只蓝袜子和两只绿袜子。如果他穿着
红色配蓝色，他穿的是相配的绿色袜子他把两个放在一起
如果他把红色和绿色配对，然后把蓝色和绿色配对，那就是不匹配的配对。鉴于
他袜子抽屉里的东西，他能放几双不相配的袜子？”
下面是一个输入示例：
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 socks2:4 socks
---> 2:4 socks---> 2:1 socks---> 2:1 socks3:4 socks---> 3:4 socks
---> 3:0 socks---> 3:0 socks4:7 socks---> 4:0 socks---> 4:0 socks
---> 4:0 socks5:11 socks---> 5:4 socks---> 5:0 socks---> 5:0 socks
------>
总计=14种可能的不匹配袜子组合。这似乎太天真了。有人对如何优化它有什么想法吗如果需要的话，我可以发布我的代码。

最佳答案

我认为通过将所有可能的袜子颜色组合成两堆，可以找到最佳的解决方案。对于每个这样的分组，可以制作奇数对袜子，其中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));
}

输出：

关于algorithm - 计算不匹配的 socks 组合总数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47046965/

SOCKS

algorithm - 计算不匹配的 socks 组合总数