Различных комбинаций с использованием различных элементов

Question

У меня есть шары разных цветов:

• 1 красных,
• 1 белых,
• 5 апельсинов,
• 2 черные,
• 0 зеленый.

Я хочу сделать алгоритм на Java, чтобы подсчитать максимальное количество комбинаций, в точности, трех разных цветов.

Например, в этом случае возможно множественное решение, но я ищу максимальное количество комбинаций. Существует 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 являются самыми большими номерами, поэтому вы должны выбрать синий, белый и красный/зеленый (неважно, выбрали ли вы красный или зеленый).

Продолжайте движение таким образом, пока у вас осталось меньше 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); 
       } 
      } 
     } 

    }