使用不同项目的不同组合

Question

我有不同颜色的球：

1 红色，
1个白色，
5 个橙子，
2 黑色,
0 绿色。

我想在 Java 中创建一个算法来计算 3 种不同颜色的最大组合数。

例如，在这种情况下，多种解决方案是可能的，但我寻找最大组合数。本例中有 2 个：

（1 红色，1 橙色，1 黑色）
（1 个白色，1 个橙色，1 个黑色）

你能建议我一个解决方案吗？谢谢！！！

Answer 1

在每个阶段只需选择您最喜欢的 3 种颜色。

例如，假设您有 2 个红色、3 个绿色、7 个蓝色、1 个黄色和 4 个白色。

你应该先挑蓝、白、绿，因为7、4、3是最大的数字。

那么你有2个红色，2个绿色，6个蓝色，1个黄色和3个白色。

6、3、2是最大的数字，所以你应该选择蓝色、白色和red/green（选择红色或绿色都无所谓）。

以这种方式继续下去，直到剩下的颜色少于 3 种，您会找到最大值。

该算法有效的正式证明非常复杂，可以找到 here。

Answer 2

这个蛮力求解算法（在 java 中）完成了工作。它很慢但可靠:

    package combinations;

    import java.util.HashMap;
    import java.util.Map;

    public class Combinations {

        private static Map<String, Integer> balls = new HashMap<String, Integer>();

        private static int maxCombinationsCount = 0;

        public static void main(String[] args)
        {
            // init
            balls.put("red",  1);
            balls.put("white", 1);
            balls.put("orange", 5);
            balls.put("black", 1);
            balls.put("green", 0);
            // begin calculation
            combine(0, 0);

            System.out.println(maxCombinationsCount);
        }

        public static void combine(int combinationCount, int combinationsCount)
        {
            for (String ball: balls.keySet()) {
                if (balls.get(ball) > 0) {
                    balls.replace(ball, balls.get(ball) - 1);
                    combinationCount ++;
                    if (combinationCount == 3) {
                        maxCombinationsCount = Math.max(maxCombinationsCount, combinationsCount + 1);
                        combine(0, combinationsCount + 1);
                    }
                    else {
                        combine(combinationCount, combinationsCount);
                    }
                    combinationCount --;
                    balls.replace(ball, balls.get(ball) + 1);
                }
            }
        }

    }

使用不同项目的不同组合

Different combinations using different items

java

algorithm

combinations