C / C ++ реализация алгоритма, аналогичного сумме подмножеств

Question

Проблема проще, чем knapsack (или ее тип, без значений и только положительных весов). Проблема состоит в проверке, может ли число быть комбинацией других. Функция должна вернуть true или false.

Например,

112 и список с { 17, 100, 101 } должен возвращать false, 469 с тем же списком должен возвращать true, 35 должен возвращать false, 119 должен возвращать true и т. Д. ..

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

Answer 1

Это особый случай задачи Сумма подмножества с наборами, которые содержат только одно отрицательное число (то есть, выражают 112 и {17, 100, 101} как {-112, 17, 100, 101}). На странице Википедии есть несколько алгоритмов, http://en.wikipedia.org/wiki/Subset_sum_problem.

Answer 2

Обратите внимание, что положительные результаты становятся плотнее по мере увеличения запрошенного числа. Например, все числа больше 100 ^ 2 могут быть сгенерированы {17, 100, 101}. Таким образом, оптимальный алгоритм может зависеть от того, много ли запрашиваемое число больше, чем члены набора. Вы можете взглянуть на теорию поля.

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

Answer 3

Наблюдение, которое поможет вам, состоит в том, что если ваш список {a, b, c ...} и число, которое вы хотите проверить, является x, то x можно записать как сумму подсписка, только если любой из x или xa можно записать как сумму подсписка {b, c, ...}. Это позволяет вам написать очень простой рекурсивный алгоритм для решения проблемы.

edit: вот код, с учетом комментариев ниже. Не проверено, поэтому, вероятно, глючит; и не обязательно самый быстрый. Но для небольшого набора данных он сделает работу аккуратно.

bool is_subset_sum(int x, std::list::const_iterator start, std::list::const_iterator end)
{
  // for a 1-element list {a} we just need to test a|x
  if (start == end) return (x % *start == 0); 

  // if x is small enough  we don't need to bother testing x - a
  if (x<a) return is_subset_sum (x, start+1, end);

  // the default case. Note that the shortcut properties of || means the process ends as soon as we get a positive.
  return (is_subset_sum (x, start+1, end) || is_subset_sum (x-a, start, end));
}

Answer 4

Если число для набора не слишком велико, вы, вероятно, можете сгенерировать все достижимые числа из набора, попадающего в диапазон [1, N].

Проблема: Доберитесь до N, используя элементы в списке L, где N достаточно мал, чтобы не волноваться о векторе размером N размера элементов.

Алгоритм:

• Создать вектор V размера N
• Для каждого элемента l в списке L
  • Для каждого достижимого элемента v в V
    • пометить все элементы v + n*l в V как достижимые