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

Question

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

Например: рассмотрим массив [1,2,3,4,5],Мне нужно найти минимальное количество значений из этого массива, сумма которых больше 5 и меньше 8. Ответ: так как 1 + 5 больше 5 и меньше 8, поэтому минимальное количество значений равно 2, следовательно, ответ.

И ниже моя функция, которая реализует логику.

int void CheckValue()
{
 for (i = 0; i <5; i++)
    if (a[i] > min && a[i] < max)
       return 1;
 for (i = 0; i< 4; i++)
     for (j = i + 1; j < 5; j++)
         if (a[i] + a[j] > min && a[i] + a[j] < max)
            return 2;


  for (i = 0; i < 3; i++)
      for (j = i + 1; j < 4; j++)
          for (k = j+1; k < 5; k++)
              if (a[i] + a[j] + a[k] > min && a[i] + a[j] + a[k] < max) 
                 return 3;
  for (i = 0; i < 2; i++)
      for (j = i + 1; j< 3; j++)
          for (k = j + 1; k< 4; k++)
              for (l = k + 1; l < 5; l++)
                  if (a[i] + a[j] + a[k] + a[l] > min && a[i] + a[j] + a[k] + a[l] < max)
                     return 4;
  if(a[0]+a[1]+a[2]+a[3]+a[4]>min && a[0]+a[1]+a[2]+a[3]+a[4]<max)
         return 5;
  return 0;
 }

Она работает нормально, но проблема в ее сложности.Может кто-нибудь дать какие-либо предложения по дальнейшей оптимизации этого кода или предоставить лучшую логику для реализации этого.

Answer 1

Я бы предложил следующее решение:

Допустим, минимальное значение диапазона равно minVal, а максимальное значение maxVal. Теперь сортируйте массив. Допустим, длина массива равна len Выполните двоичный поиск числа в массиве, которое просто <= maxVal. </p>

Пропуск поиска: Я имею в виду, что если число находится в индексе i, то число в индексе i + 1 должно быть> = maxVal. Допустим, индекс этого числа равен currIndex. Если это число равно maxVal, тогда выполните бинарный поиск от 0 до currIndex для числа

минВал и

Ошибка поиска: Это среднее значение для массива меньше, чем maxVal. Поэтому для этого случая выполните следующие действия: 1) Добавьте наибольшее число в массиве к набору результатов. 2) Теперь начните цикл с len-1 t0 1. Если arr [len-1] + arr [len] меньше maxVal, тогда добавьте arr [len-1] в результирующий набор и продолжите цикл. Если arr [len-1] + arr [len]> maxVal, пропустите и проверьте наличие arr [len-1] + arr [len].

и т. Д.

Answer 2

Это домашнее задание?

Ваш вопрос действительно неясен, но вот что я хотел бы:

Сортировка. NlogN .
Начните с добавления первого элемента и последнего элемента. Это в диапазоне? Возьмите первый указатель с одного конца, скажем, с начала, переместите его в середину и добавьте среднее число и последнее число, первый указатель + последний указатель. это в диапазоне? Вы можете переместить первый указатель в середину между первым и последним указателем, то есть: вправо на 3/4 последовательности.

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

Это даст вам приблизительное количество элементов, которые будут в диапазоне. Я надеюсь, у вас есть идея.

Вы можете переместить второй указатель в середину, если ваша сумма выходит за пределы диапазона.

Это даст вам nlogn .

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

два числа легко, nlogn делает это

Все возможные подмножества являются проблемой суммы подмножеств, которая составляет np hard . экспонента, которая составляет 2 ** n .

Answer 3

У меня нет никакого опыта в таких вещах, поэтому, вероятно, есть лучшие способы сделать это, но у меня есть некоторые идеи, которые могут быть полезны.

В настоящее время вы вычисляете каждыйвозможная комбинация, вы должны иметь возможность изменить свой алгоритм так, чтобы вы могли исключать некоторые комбинации без необходимости их вычисления.

Я бы сначала отсортировал массив, что позволит вам исключить некоторые значения безвычисляя их.

Например, если у вас есть массив, который выглядит как [1,2,4,5,9] и min = 11 и max = 14, тогда ваш алгоритм проверит 1 + 2,1 +4,1 + 5,1 + 9, затем 2 + 4, 2 + 5, 2 + 9, 4 + 5, 4 + 9, прежде чем прийти к ответу.

Если вместо этого вы сначала начнете с наибольшего числа, вы можете исключить все возможные комбинации 1, выполнив вычисления 9 + 1, так как 9 + 1 <= 11, это должно быть так, что все остальные возможные комбинации 1 недействительныдля суммы двух чисел, то же самое со всеми возможными 2 комбинациями.Если вы добавите такую ​​логику в свой код, у вас должно быть меньше лишних вычислений, надеясь ускорить ваш код.</p>

Answer 4

Это довольно сложная проблема, которая может быть сложной.

Одна вещь, которая приходит на ум, это то, что она немного напоминает «проблему с рюкзаком». Возможно, вы сможете найти реализацию этого и адаптировать ее.

---

Если ожидается, что минимальное количество предметов будет небольшим, вы, конечно, можете использовать метод грубой силы:

1. Установить minVal = 1
2. Найти все наборы размера minVal
3. Пока ни один из наборов не соответствует вашим критериям, добавьте 1 к minVal и перейдите к шагу 2

Answer 5

Я думаю, вам стоит рассмотреть сортировку массива, для этого есть много эффективных алгоритмов.

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