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

Question

彩色2->3只袜子

彩色3->7只袜子

彩色4->11袜子

1:3袜子---->1:3袜子---->1:0袜子---->1:0袜子

2:4袜子---->2:4袜子---->2:1袜子---->2:1袜子

3:4袜子-->3:4袜子-->3:0袜子-->3:0袜子

4:7袜子-->4:0袜子-->4:0袜子-->4:0袜子-->4:0袜子

5:11袜子---->5:4袜子---->5:0袜子---->5:0袜子

------>总计=14种不匹配袜子的可能组合。这似乎太天真了。有没有人对如何优化有什么想法？如果需要，我可以发布我的代码。

Answer 1

我认为最优的解决方案可以通过检查所有可能的分组不同的袜子颜色成2堆。对于每一个这样的分组，P可以制作奇数双袜子，其中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