Расчет серии

У меня есть несколько случайных чисел, таких как

99 20 30 1 100 400 5 10

Я должен найти сумму из любой комбинации этих целых чисел, которая ближе всего (равна или больше, но не меньше) к данному числу, как

183

Какой самый быстрый и точный способ сделать это?

Источник

6 ответов

Решение

Если ваши цифры невелики, вы можете использовать простую технику динамического программирования (DP). Не позволяй этому имени напугать тебя. Техника довольно понятна. В основном вы разбиваете большую проблему на подзадачи.

Здесь мы определяем проблему как can[number], Если number может быть построен из целых чисел в вашем файле, то can[number] является trueв противном случае это false, Очевидно, что 0 можно построить без использования каких-либо чисел, поэтому can[0] является true, Теперь вы пытаетесь использовать каждое число из входного файла. Мы пытаемся увидеть, если сумма j достижимо Если already achieved sum + current number we try == j, затем j явно достижимо. Если вы хотите отслеживать, какие числа составили конкретную сумму, используйте дополнительный prev массив, в котором хранится последнее использованное число для суммирования. Посмотрите код ниже для реализации этой идеи:

int UPPER_BOUND = number1 + number2 + ... + numbern //The largest number you can construct
bool can[UPPER_BOUND + 1]; //can[number] is true if number can be constructed
can[0] = true; //0 is achievable always by not using any number

int prev[UPPER_BOUND + 1]; //prev[number] is the last number used to achieve sum "number"
for (int i = 0; i < N; i++) //Try to use every number(numbers[i]) from the input file
{
   for (int j = UPPER_BOUND; j >= 1; j--) //Try to see if j is an achievable sum
   {
      if (can[j]) continue; //It is already an achieved sum, so go to the next j

      if (j - numbers[i] >= 0 && can[j - numbers[i]]) //If an (already achievable sum) + (numbers[i]) == j, then j is obviously achievable
      {
          can[j] = true;
          prev[j] = numbers[i]; //To achieve j we used numbers[i]
      } 
   }
}

int CLOSEST_SUM = -1;
for (int i = SUM; i <= UPPER_BOUND; i++)
   if (can[i])
   {
       //the closest number to SUM(larger than SUM) is i
       CLOSEST_SUM = i;
       break; 
   }

int currentSum = CLOSEST_SUM;    
do
{
    int usedNumber = prev[currentSum];
    Console.WriteLine(usedNumber);

    currentSum -= usedNumber;
} while (currentSum > 0);
Источник

Похоже, это проблема типа рюкзака, где значение ваших целых чисел будет равно "весу" каждого предмета, "прибыль" каждого предмета равна 1, и вы ищете наименьшее количество предметов, которое точно суммируется в максимально допустимый вес рюкзака.

Источник

Это вариант проблемы SUBSET-SUM, а также NP-Hard, такой как SUBSET-SUM.

Но если задействованные числа малы, существуют алгоритмы псевдополиномиального времени. Проверять, выписываться:

http://en.wikipedia.org/wiki/Subset_sum_problem

ОК Подробнее.

Следующая проблема:

Для данного массива целых чисел и целых чисел a, b существует некоторое подмножество, сумма которого лежит в интервале [a,b], является NP-трудной.

Это так, потому что мы можем решить сумму подмножеств, выбрав a = b = 0.

Теперь эта проблема легко сводится к вашей проблеме, и поэтому ваша проблема тоже NP-Hard.

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

Учитывая массив из N целых чисел, цель S и порог аппроксимации c,

существует алгоритм аппроксимации полиномиального времени (включающий 1/c), который сообщает, существует ли сумма подмножеств в интервале [(1-c)S, S].

Вы можете использовать это несколько раз (с помощью бинарного поиска), чтобы найти наилучшее приближение к S, которое вам нужно. Обратите внимание, что вы также можете использовать это на интервалах от [S, (1+c)S], тогда как рюкзак даст вам решение <= S.

Конечно, могут быть и лучшие алгоритмы, на самом деле я могу поспорить на это. В сети должно быть много литературы. Некоторые поисковые термины, которые вы можете использовать: алгоритмы аппроксимации для суммы подмножеств, алгоритмы псевдополиномиального времени, алгоритм динамического программирования и т. Д.

Источник

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

Более быстрым решением было бы отсортировать числа, а затем... Добавить наибольшее число к вашей сумме. Это слишком большое? если это так, снимите его и попробуйте следующий маленький. если сумма слишком мала, добавьте следующее наибольшее число и повторите. Продолжайте добавлять числа, не позволяя сумме превысить цель. Готово, когда вы попали в цель.

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

Источник

Вы можете отсортировать список значений, найти первое значение, которое больше цели, и начать концентрироваться на значениях, которые меньше цели. Найдите сумму, ближайшую к цели, не переходя, затем сравните ее с первым значением, большим, чем цель. Если разница между ближайшей суммой и целью меньше, чем разница между первым значением, большим, чем цель и цель, то у вас есть ближайшая сумма.

В некотором роде, но я думаю, что логика висит вместе.

Источник

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

nums = {99, 20, 30 , 1, 100, 400, 5, 10};
vars = a /@ Range@Length@nums;
Minimize[(vars.nums - 183)^2, vars, Integers]
Источник
Другие вопросы по тегам