2

Есть массив со строками, в котором может быть 60-100 элементов(15-20 элементов, с качеством от 1 до 5), нужно из них собрать уникальные ряды из 10 элементов. Порядок элементов в ряде не важен. То есть:

1,2,3,4,5,6,7,8,9,10 = 10,9,8,6,7,5,4,3,2,1 = 8,9,10,7,6,4,5,3,1,2 - Одни и те же ряды.

Каждому элементу массива [1,2,3...] соответствуют массивы с названием элемента [Яблоко, Апельсин, Арбуз...], качество [1-5,1-5,1-5...] его цена [20,40,10...] и то, что может получиться из данного элемента [яблочный сок - 20$|салат из яблок - 30$, апельсиновый фрэш -50$, арбузный лимонад - 10$, арбузный десерт - 30$]. От среднего качества ряда качества зависит стоимость выходящего элемента. К примеру если качество ряда 1, то цена выходящего элемента, к примеру, будет 50$, 2 -60$, 3 - 75$, 4 - 130$, 5 - 250$. То есть у каждого выходящего элемента есть 5 качеств и 5 цен соответственно.

В результате нужно получить Среднее арифметическое качества ряда, среднюю цену элементов, шанс получения каждого продукта, и среднюю цена выходящего продукта.

К примеру, если на выходе 5 разных вариантов, то шанс салат из яблок - 20%. И нужно в зависимости от шанса получить среднюю выходящую стоимость.

Если все 10 элементов в ряде - яблоки, то шанс на салат и на яблочный сок - 50/50. Если 9 яблок и 1 апельсин, то 90% - салат и сок(45% салат и 45% сок), а 10% - апельсиновый фрэш. Если 8 яблок, 1 апельсин и 1 арбуз, то 80% - сок или салат, 10% - фрэш, 10% - арбузный лимонад или дессерт. Из каждого продукта, получается от 1 до 5-7 разных блюд

К примеру шанс получить яблочный сок и салат = 16.66%, а апельсиновый фрэш 33.33%. Выходящая стоимость будет 0.166x20 + 0.166x30 + 0.33x50 ... = n.

И потом отсортировать по выгодности, в зависимости от того, сколько было затрачено на продукты, и сколько в среднем может получиться на выходе. Таким образом найти оптимальные сочетания продуктов

Как лучше это реализовать, чтобы программа не выполнялась вечность?

10
  • Можете указать все арифметические формулы, решение сильно зависит от них. Еще, расскажите подробнее какой должен быть результат: максимальная сумма, выборка с максимальной суммой, лучшие десять подборок или полный список сочетаний? Полный список строить проблематично, скажу сразу. 6 авг 2020 в 7:08
  • Никита я понимаю что вы хотите абстрагировать задачу. Но поверьте это не всегда помогает. Дайте примеры не нужно все в реальности считать подсчитывать и т.д. Просто напишите как будто объясняете "дауну" извините конечно. Ответ очень сильно зависит от вопроса. 6 авг 2020 в 7:11
  • Обновил описание, думаю так будет понятнее. Просто всё полностью объяснить слишком сложно будет. Но суть примерно такова. 6 авг 2020 в 7:24
  • @НикитаМостоцкий Задача усложняется, боюсь будет много вопросов. Сколько всего разных блюд? Бывают ли блюда из нескольких ингридиентов или все из одного? Можно ли дублировать элементы в ряду (взять два яблока — одно на сок, другое на салат)? Может, попробуете этот пример с фруктами и продуктами разобрать полностью, от начала до конца? Сочетаний немного, а задача станет яснее. 6 авг 2020 в 7:35
  • 1
    @defaultlocale дополнил 6 авг 2020 в 7:43

1 ответ 1

0

Решил вот таким образом, но при увеличении массива больше 13-14 элементов уже очень сильно возрастает время выполнения. Как уменьшить время выполнения пока не решил

   static void combination(int[] a, int n) {
    int size = a.length;
    int[] selected = new int[n];
    new Object() {

        void print() {
            for (int i = 0; i < n; ++i){
                System.out.print(a[selected[i]] + " ");
                // будущие операции
            }
            System.out.println();
        }

        void combination(int index, int prev) {
            if (index >= n)
                print();
            else
                for (int i = prev; i < size; ++i)
                    combination(index + 1, selected[index] = i);
        }

    }.combination(0, 0);

    private void jLabel15MouseClicked(java.awt.event.MouseEvent evt) { 
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        combination(a, 10);
    }   
1
  • Жалко что нет самого интересного, т.е. расчета формул и отображения результата. Перебор всех сочетаний плохо масштабируется, но с формулами, возможно найдется аналитическое решение без перебора. 7 авг 2020 в 7:35

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.