Описание тега subset-sum
In computer science, the subset sum problem is one of the important problems in complexity theory and cryptography.
2
ответа
Разделить подмножество с ограничением
Сегодня, практикуя некоторые вопросы Алгоритма, я нашел интересный вопрос. Вопрос в том Вы должны разделить 1 на n (с одним пропущенным значением x) на две равные половины, так что сумма двух половин равна. Пример: Если n = 7 а также x = 4 Решение б…
11 янв '18 в 05:19
1
ответ
Наименьшая денежная сумма, которую можно получить, используя только монеты указанного достоинства, превышающие пороговое значение
Другими словами, дан набор из n натуральных чисел A и порог BЯ хочу найти самый маленький C чтобы: C > B C = A[1] * k[1] + A[2] * k[2] + ... + A[n] * k[n], k[i] целые числа>= 0 В качестве примера, если A = { 6, 11, 16 } тогда значения, которые мы…
09 янв '18 в 16:22
3
ответа
Как работает это решение задачи о подмножестве сумм?
Это решение проблемы подмножества сумм. Он использует возврат. Я думал об этом более 2 часов, и я просто не могу этого понять. редактировать: я добавил несколько комментариев к коду на основе того, что я понял. Пожалуйста, поправьте меня, если я оши…
20 ноя '11 в 17:44
0
ответов
Эффективно связывать объекты на сетке
Учитывая матрицу nXn. И учитывая некоторые объекты различных форм / размеров, как указано ниже. Как я могу эффективно связать все объекты в сетке? Формы, как показано на этом изображении: "связать" означает расположение объектов в сетке nXn. Объект …
10 ноя '13 в 10:45
0
ответов
Разбиение множества на K подмножеств с равной суммой
Я собираюсь выполнить упражнение, чтобы разбить множество на K подмножеств с равной суммой. Скажем Input : arr = [2, 1, 4, 5, 6], K = 3 Output : Yes we can divide above array into 3 parts with equal sum as [[2, 4], [1, 5], [6]] Я нашел решение здесь…
29 ноя '17 в 16:49
1
ответ
Алгоритмы. Динамическое программирование. Подмножество двух массивов
Моя домашняя работа включает в себя вопрос динамического программирования: Даны два массива натуральных целых чисел (a1,a2,...,an и b1,b2,...,bn), все они меньше n^2, а также задано число B, которое меньше n^3. Вам нужно сдерживать, если есть массив…
14 дек '15 в 06:30
1
ответ
Сумма подмножества с положительными и отрицательными целыми числами
Я должен реализовать вариант задачи суммы подмножеств, мой вклад будет положительным и отрицательным десятичным, также мне нужно будет знать подмножество, зная, что, к сожалению, существует, этого недостаточно. Я пробовал алгоритмы, найденные в Вики…
14 май '14 в 09:22
2
ответа
R expand.grid с ограничениями на ряд
У меня есть числовой вектор x длины N, и я хотел бы создать вектор из заданных сумм всех следующих наборов: любая возможная комбинация элементов x, содержащая не более M элементов в каждой комбинации. Я собрал медленный итеративный подход; то, что я…
28 ноя '16 в 12:09
0
ответов
Доказательство Н. П. Полноты проблемы разбиения множества
Я уменьшил проблему суммы подмножеств, чтобы установить проблему с разделами, но не знаю, является ли она правильной, и поэтому мне нужна ваша помощь.МОЙ МЕТОД:В задаче о сумме подмножества мы должны найти подмножество S1 из множества S, чтобы оно с…
29 ноя '18 в 21:17
0
ответов
Найти значения, которые равны 0 в Excel со многими элементами
Я должен найти каждое подмножество в достаточно большом списке, 500/1000 элементов, которые являются положительными и отрицательными и являются десятичными, а сумма равна 0. Я не эксперт, поэтому я прочитал много и много статей и решений, а затем я …
16 ноя '18 в 10:58
0
ответов
Определение частного случая подмножества с осложнениями
У меня есть проблема, о которой у меня есть ряд вопросов. Во-первых, я в основном ищу помощь в описании и понимании проблемы. Решения всегда приветствуются, но самое главное, я мог бы воспользоваться советом от кого-то более опытного, чем я. Теперь,…
09 окт '14 в 02:54
2
ответа
Расчет суммы нескольких подмножеств
У меня есть 2 набора, набор A содержит множество случайных чисел, а элементы набора B представляют собой сумму подмножеств набора A. Например, A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] B = [183, 36, 231, 128, 137] Я хочу найти, …
23 фев '17 в 17:56
2
ответа
Получить все подмножества, которые суммируют до значения N в прологе
Это постановка проблемы: Учитывая список целых чисел L и целое число S, генерировать все подсписки, элементы которых составляют до S. Это мое решение: domains list=integer* clist=list* predicates sum(list,integer) check(clist,clist,integer) gensub(l…
20 ноя '13 в 10:05
3
ответа
Фильтрация дубликатов в комбинациях сумм подмножеств
Учитывая массив, я нашел все комбинации подмножеств, которые равны целевой сумме, потому что я хочу максимально возможный массив. Например, массив [1, 2, 2, 2] для целевой суммы "4" возвращает [[2, 2], [2, 2], [2, 2]]. subsets = [] def subset_sum(nu…
05 дек '17 в 03:16
7
ответов
Разделите массив на k непрерывных разделов так, чтобы сумма максимального раздела была минимальной
Здесь подмножество максимальной суммы является одним из k подмножеств, которые дают максимальную сумму, например: arr = [10,5,3,7] и k = 2 возможных способа разделить arr на k подмножеств: {10, [5,3,7]}, {[10,5], [3,7}, {[10,5,3], 7} и {[10,5], [3,7…
24 сен '16 в 07:47
1
ответ
Возвращать комбинации обратно из запомнившегося алгоритма сумм подмножеств?
Я работал над основной проблемой суммы подмножеств. Учитывая сумму, скажем, 6, и числа [1,2,3,4,5,6]), мне нужно было найти общее количество комбинаций, которые составили s (для s=6: [1,5], [2,4], [1,2,3]). Мне удалось решить это с помощью грубой си…
19 окт '16 в 21:23
0
ответов
Оптимизация Ant Colony для поиска подмножеств с суммой ~0
У меня есть множество A = [x1, x2...xn], где xi в R (вещественное). Мне нужно найти все непересекающиеся подмножества с суммой подмножеств ~0. Поскольку в наборе могут быть ненулевые действительные числа, я решил использовать Ant Colony Optimization…
01 мар '19 в 04:25
1
ответ
Сведение проблемы подмножества сумм только к положительным числам
Я хочу знать, есть ли способ уменьшить проблему суммы подмножеств с набором "A" с отрицательными и положительными целыми числами до той же задачи, но только с положительными числами.
23 апр '14 в 16:12
5
ответов
Разделение списка в прологе
Я пытаюсь создать предикат Prolog, в котором по заданному списку видно, можно ли разделить этот список на два списка, которые суммируются в одну и ту же сумму. У меня есть предикат суммы рабочего списка, поэтому я использую его в своем предикате раз…
01 апр '15 в 18:54
1
ответ
Алгоритм нахождения минимального числа N для разбиения значений стека на подмножества X с суммой ниже, чем N
У меня есть стек с целочисленными значениями объектов. Я хочу купить грузовик грузоподъемностью N( N неизвестен), чтобы быть уверенным, что я могу перевозить все объекты на максимальных X кругах. Х известен. Другими словами, я должен разделить стек …
09 май '18 в 19:32