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

Question

这是 2015 年 ICPC 西北编程竞赛的问题之一，我想知道是否有更简单或更有效的方法来做这件事。

问题是:

“Fred 喜欢穿不搭配的 socks 。这有时意味着他必须提前计划。 假设他的 socks 抽屉里有一只红色、一只蓝色和两只绿色 socks 。如果他穿 红色搭配蓝色，他穿的是相配的绿色 socks 。他把两个 如果他将红色与绿色配对，然后将蓝色与绿色配对，则会出现不匹配的配对。鉴于 他 socks 抽屉里的东西，他能放多少双不匹配的 socks ？”

这是一个示例输入:

颜色 1 -> 4 socks

颜色 2 -> 3 socks

颜色 3 -> 7 socks

颜色 4 -> 11 socks

颜色 5 -> 4 socks

我的做法是首先将输入读入一个数组，然后按递增方式对它进行排序。这样我就会在数组的末尾拥有最多数量的 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 种可能的不匹配 socks 组合。这种方法似乎太天真了。有没有人对如何优化它有任何想法？如有必要，我可以发布我的代码。

Answer 1

我认为可以通过检查所有可能的将不同颜色的 socks 分成两堆来找到最佳解决方案。对于每个这样的分组，可以制作 p 奇数双 socks ，其中 p 是最小堆中 socks 的数量。您想要给出最大 p 的分组。您可以递归地将所有可能的 socks 分组生成 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