Расчет серии

Question

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

99 20 30 1 100 400 5 10

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

183

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

Answer 1

Если ваши цифры маленькие, вы можете использовать простую технику Динамическое программирование (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);

Answer 2

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

Answer 3

Это вариант задачи SUBSET-SUM, а также NP-Hard, такой как SUBSET-SUM.

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

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

Ok Подробнее.

Следующая задача:

Задан массив целых чисел, а целые числа 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. </p>

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

Answer 4

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

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

Answer 5

Если числа большие, вы можете превратить это в целочисленную программу.Используя Mathematica s solver, он может выглядеть примерно так

nums = {99, 20, 30 , 1, 100, 400, 5, 10};
vars = a /@ Range@Length@nums;
Minimize[(vars.nums - 183)^2, vars, Integers]

Answer 6

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

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