Вопросы по теме 'subset-sum'
Легче ли решить этот вариант задачи о сумме подмножеств?
У меня проблема, связанная с проблемой суммы подмножества , и мне интересно, облегчают ли эти различия различия, т. Е. разрешима в разумные сроки.
Учитывая значение V, размер набора L и последовательность чисел [1, N] S, сколько подмножеств...
7729 просмотров
schedule
02.10.2022
Найдите элементы массива на основе минимальной суммы
Я написал цикл на C++, чтобы получить 6 случайных чисел и сохранить их в массиве. Я хотел бы суммировать элементы массива до тех пор, пока не получу значение, превышающее число «x», но я хотел бы сделать это без необходимости добавления всех...
2794 просмотров
schedule
06.05.2023
Максимальная сумма подмножества с двумя массивами
Я даже не уверен, что это можно сделать за полиномиальное время.
Проблема:
Даны два массива действительных чисел,
A = (a[1], a[2], ..., a[n]),
B = (b[1], b[2], ..., b[n]), (b[j] > 0, j = 1, 2, ..., n)
и число k , найти...
1001 просмотров
schedule
14.04.2022
Нахождение подмножества, удовлетворяющего определенному условию
У меня есть несколько массивов чисел (каждый элемент массива может принимать значение только 0 или 1), как это
v1: 1; 0; 0; 1; 1;
v2: 0; 1; 0; 0; 1;
v3: 1; 1; 0; 1; 0;
v4: 1; 0; 0; 1; 0;
v5: 1; 1; 0; 1; 1;
v6: 1; 1; 0; 1; 1;
Я хочу...
595 просмотров
schedule
02.01.2023
максимальная сумма подмножества размера K с суммой меньше M
Дано: массив целых значений K, M
Вопрос: Найдите максимальную сумму, которую мы можем получить из всех подмножеств K элементов данного массива, такая, что сумма меньше значения M?
Есть ли решение этой проблемы без динамического программирования?...
10286 просмотров
schedule
16.04.2022
Найдите сумму подмножества с умножением
Допустим, у нас есть набор
{a_1, a_2, a_3, ..., a_n}
Цель состоит в том, чтобы найти сумму, которую мы создаем следующим образом: мы находим все подмножества, длина которых равна 3, затем умножаем элементы каждого подмножества (для...
1659 просмотров
schedule
15.06.2023
Нижняя граница и удаление хеширования для поиска подмножества размера 4, которое добавляется к целевой сумме
Поиск подмножества из четырех элементов, которые добавляются к целевой сумме S, может быть выполнен за время O (n ^ 2) путем хэширования всех попарных сумм x, а также хеширования S - x до тех пор, пока не будет найдено нетривиальное столкновение....
61 просмотров
schedule
05.09.2022
Алгоритм подмножества-суммы с вычитанием
У меня есть проблема с суммой подмножества, где вы можете добавлять или вычитать условия. Например, если у меня есть пять членов (1, 2, 3, 4, 5), я хочу знать, сколько способов я могу сложить/вычесть члены, чтобы получить 7:
3 + 4
2 + 5
1 +...
677 просмотров
schedule
28.10.2022
Поиск подмножества с максимальным значением, в котором алгоритм PartitionProblem возвращает true
У меня есть следующее задание.
У вас есть мультимножество S, состоящее из 1‹=N‹=22 элементов. Каждый элемент имеет положительное значение до 10000000.
Предположим, что существуют два подмножества s1 и s2 множества S, в которых сумма значений...
567 просмотров
schedule
31.01.2023
Сложность суммы подмножества с несколькими целями
Является ли следующая проблема в NP-Complete или P? Входные данные : набор S положительных целых чисел {a1, a2, ..., an) и положительное целое число M Вопрос : существует подмножество S' множества S такое, что сумма всех элементов S' равна M-1,...
279 просмотров
schedule
15.04.2022
Сумма подмножества Пролог
Определите подмножество предикатов (L, Sum, Subl), которое принимает список L чисел, число Sum и объединяет SubL с подпоследовательностью L, так что сумма чисел в SubL равна Sum.
Например
?- subsetsum([1,2,5,3,2], 5, SubSet);
SubSet =...
2132 просмотров
schedule
09.08.2023
Как вы узнаете, является ли k постоянным для O (n ^ k) в сумме подмножества?
Проблема суммы подмножества: задан набор чисел S и целевое число, скажем, 0 . Цель состоит в том, чтобы найти подмножество S’ из S такое, что элементы в нем составляют в сумме 0 . Я слышал, что эта задача становится полиномиальной, если...
146 просмотров
schedule
01.04.2022
Сумма подмножества с поиском по окрестностям — Java
Я пытаюсь реализовать проблему суммы подмножества, используя алгоритм соседства. Вот псевдокод:
1. Generate a random solution for the problem and call it S
2. Compute the neighborhood of S and choose S' as the best solution in the neighborhood
3....
301 просмотров
schedule
28.07.2023
Фильтрация дубликатов в комбинациях суммы подмножества
Учитывая массив, я нашел все комбинации подмножеств , которые равны целевой сумме, потому что мне нужен максимально большой массив.
Например, массив [1, 2, 2, 2] для целевой суммы «4» возвращает [[2, 2], [2, 2], [2, 2] ]] .
subsets = []...
453 просмотров
schedule
11.02.2023
Подзадачи суммы перекрывающихся подзадач (динамическое программирование)
Ссылка на вопрос выглядит следующим образом: https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ Я не вижу, чтобы свойство перекрывающейся подзадачи выполнялось в вопросе, по крайней мере, для любого случая ввода. Например, в...
250 просмотров
schedule
27.10.2023
Найдите все комбинации набора чисел, которые в сумме дают определенную сумму
Я видел несколько решений подобных проблем, но все они требуют повторения количества элементов, которые нужно сложить вместе.
Вот моя цель: из списка чисел найти все комбинации (без замены), которые в сумме дают определенную сумму. Например, если...
4155 просмотров
schedule
14.01.2023
Восстановление массива
Недавно я столкнулся с этим вопросом в конкурсе найма:
Дан массив S из 2^N целых чисел (1 ‹= N ‹= 20, 0 ‹= Si ‹= 10^9), представляющий суммы подмножеств массива A, нам нужно восстановить массив A в отсортированном порядке.
например S = {2, 1,...
54 просмотров
schedule
06.07.2022
Как найти элементы в массиве, сумма которых равна или меньше и ближе к заданному значению?
Я хочу найти элементы в заданном массиве положительных целых чисел так, чтобы их сумма была меньше или равна заданному значению T. Когда оно меньше T, оно должно быть ближайшим к значению T. Я надеюсь, что это вариант задачи о сумме подмножеств в...
192 просмотров
schedule
22.05.2023
Подсчитайте целые разделы с k частями, когда заданы элементы раздела
Я хочу подсчитать целые разделы n с k элементами раздела. Возможные элементы раздела определяются через данный вектор v с различными элементами. Элементы перегородки можно выбирать более одного раза. Как я могу это сделать? Оптимально без...
109 просмотров
schedule
24.03.2022
Правильное определение проблемы суммы подмножества
Читая книгу Ганса Келлерера, Ульриха Пферши и Дэвида Пизингера Проблемы с рюкзаком , издание 2004 года, о проблеме суммы подмножеств, я нашел это определение (глава 4):
Дан набор N = {1, ..., n} из n элементов с положительными целыми весами...
90 просмотров
schedule
18.04.2022
