Вопросы по теме 'subset-sum'
SUBSET-SUM, верхняя граница количества решений
Как вы, наверное, знаете, проблема SUBSET-SUM определяется как определение того, является ли сумма подмножества набора целых чисел заданным целым числом. (есть другое определение суммы подмножества, где сумма группы целых чисел равна нулю, но...
1030 просмотров
schedule
18.05.2022
Как мне найти все наборы из N однозначных неповторяющихся чисел, которые в сумме дают заданную сумму в PHP?
Допустим, я хочу найти все наборы из 5 однозначных неповторяющихся чисел, которые в сумме дают 30... В итоге я получу [9,8,7,5,1], [9,8,7 ,4,2], [9,8,6,4,3], [9,8,6,5,2], [9,7,6,5,3] и [8,7,6, 5,4]. Каждый из этих наборов содержит 5 неповторяющихся...
4488 просмотров
schedule
25.07.2023
Решение проблемы суммы подмножества с большими суммами и десятичными знаками
Поиск решения проблемы суммы подмножества для этого конкретного случая (в С# или другом алгоритме):
1) В наборе около 1000 номеров (может вырасти до нескольких тысяч)
2) Суммы исчисляются миллиардами
3) Числа представляют собой денежные...
1612 просмотров
schedule
07.07.2022
проблема с пользовательским разделом
Может ли кто-нибудь подсказать мне, как решить эту проблему.
Нам дано множество S, в котором содержится k элементов.
Теперь нам нужно разбить множество S на x подмножеств так, чтобы разница в количестве элементов в каждом подмножестве была не...
1961 просмотров
schedule
09.06.2023
Алгоритм: оптимальное сочетание значений, чтобы оставаться в пределах допустимого диапазона
У меня есть следующая математическая задача, которая мне нужна в приложении, и мне интересно, есть ли эффективный способ найти наилучшее решение, а не приближение.
У меня есть список положительных и отрицательных значений.
Сумма этих значений...
477 просмотров
schedule
27.03.2023
сумма подмножества из рекурсивного поиска с возвратом
Я пытаюсь изменить вопрос «Список всех комбинаций в строке» для проблемы, когда нам нужно напечатать все наборы, которые имеют заданную «сумму». Вот мой исходный код, но я не уверен, как сохранить список наборов в коде:
/**
* method to return...
2316 просмотров
schedule
09.07.2023
найти решение суммы подмножества с помощью динамического программирования
Чем я хочу заниматься
Я хочу найти подмножество массива, которое суммируется с целью T . Я также хочу использовать для этого подход динамического программирования (и решение снизу вверх).
Что у меня сейчас есть
В настоящее время я...
13092 просмотров
schedule
06.09.2022
Сумма кратных чисел больше или равна цели, оптимизация
Учитывая уравнение
Как 2(p 1 ) + 3(p 2 ) + 7(p 3 ) >= 257
Мне нужно найти все возможные комбинации p 1 , p 2 , p 3 , чтобы приведенное выше утверждение было истинным, а результирующая сумма (левая рука часть уравнения ) минимальна, если...
205 просмотров
schedule
25.09.2022
Подсчитайте количество подмножеств с суммой, равной k
Для данного массива нам нужно определить количество подмножеств, сумма которых в точности равна заданному целому числу k. Подскажите, пожалуйста, оптимальный алгоритм решения этой проблемы. Здесь фактические подмножества не нужны, достаточно...
13283 просмотров
schedule
15.08.2022
Уменьшите сумму подмножества до полимино-упаковки
Это домашнее задание, поэтому любая помощь приветствуется.
Мне нужно доказать, что следующая задача является NP-полной. Подсказка говорит, что вы должны свести задачу суммы подмножества к этой задаче.
Имея набор фигур, как показано ниже, и...
683 просмотров
schedule
17.01.2023
Улучшение этого алгоритма суммирования подмножества для последовательного диапазона без использования рекурсии
Учитывая min и max , я хотел бы найти каждую комбинацию чисел в этом диапазоне, которая в сумме дает заданное total , используя указанное число bins (повторное использование чисел в порядке). Количество бинов приблизится, но не превысит 32, так...
118 просмотров
schedule
11.05.2023
Найдите числа, которые нужно исключить из набора, чтобы сделать два подмножества, числа которых в сумме дают одно и то же значение [дубликаты]
Проблема в следующем:
Вам дан набор положительных целых чисел {a1, a2, a3, ..., an}, в котором могут быть повторяющиеся числа, например, A = {6, 30, 3, 11, 3}. Мне нужно разбить числа на два подмножества, чтобы сумма всех чисел в каждом...
23 просмотров
schedule
13.10.2022
Нахождение максимального значения взвешенной суммы подмножества набора мощности
У меня разреженный набор мощности для ввода (т.е. некоторые комбинации были предварительно исключены). Каждая запись в наборе мощности имеет определенный балл. Я хочу найти комбинацию, которая покрывает все точки и максимизирует общий балл....
326 просмотров
schedule
09.10.2023
Временная сложность перечисления суммы подмножества
Обычно при работе с комбинациями сложность Big-O кажется равной O(n Choose k) . В этом алгоритме я генерирую все комбинации в массиве, которые соответствуют целевой сумме:
def combos(candidates,start, target):
if target == 0:
return...
2667 просмотров
schedule
25.05.2023
Haskell получает все числа, сумма которых равна X
Мне нужно создать функцию в haskell, которая получает число и возвращает список списков, где в списке есть все комбинации чисел, сумма которых равна полученному числу.
трудно объяснить, так что это пример:
sum1 4 = [ [4], [3,1], [2,2], [1,3],...
775 просмотров
schedule
09.08.2022
Рекурсия для поиска n чисел в диапазоне, которые в сумме составляют целевое значение
Я написал функцию, которая находит все наборы из двух чисел, которые суммируют целевое значение, учитывая диапазон чисел от 0 до x. Я пытаюсь переписать его таким образом, чтобы вы могли получить результат заданной длины n (не только 2), но n чисел,...
1240 просмотров
schedule
10.08.2023
Сумма произведений всех возможных подмножеств массива
Я написал код, чтобы найти сумму произведения всех возможных подмножеств массива. Я получаю ожидаемый результат, но не могу сделать это достаточно быстро, чтобы очистить тестовые примеры, связанные со временем.
Может ли кто-нибудь помочь мне...
992 просмотров
schedule
15.03.2023
Суммируйте каждое уникальное значение одного столбца для каждого уникального значения в другом столбце R
Пример моего фрейма данных:
df<- structure(list(Var1 = c("A-01", "A-01", "A-02", "A-01", "A-02",
"A-03", "A-01", "A-02", "A-03", "A-04", "A-01", "A-02", "A-03",
"A-04", "A-05", "A-01", "A-02",...
215 просмотров
schedule
11.06.2024
Уменьшить сложность задачи последовательности с экспоненциальной до полиномиальной?
Я работаю над следующей проблемой :
Учитывая набор неотрицательных различных целых чисел и значение m, определите, существует ли подмножество данного набора с суммой, кратной m.
Ввод: первая строка ввода содержит целое число T,...
151 просмотров
schedule
28.12.2022
Доказательство NP-полноты задачи о множестве-разбиении
Я сократил задачу о сумме подмножества до задачи о разделе, но не знаю, правильно ли это, поэтому мне нужна ваша помощь. МОЙ МЕТОД : В задаче о сумме подмножества мы должны найти подмножество S1 множества S так, чтобы оно суммировалось с числом t, и...
569 просмотров
schedule
13.03.2023
