Вопросы по теме 'subset-sum'
Проблема суммы подмножеств и разрешимость NP-полных задач
Я читал о проблеме подмножества сумм, когда придумал, как представляется, универсальный алгоритм для ее решения:
(defun subset-contains-sum (set sum)
(let ((subsets) (new-subset) (new-sum))
(dolist (element set)
(dolist...
1734 просмотров
schedule
30.09.2022
Найдите минимальное количество необходимых элементов, чтобы их сумма была равна или больше S
Я знаю, что это можно сделать, отсортировав массив и взяв большие числа, пока не будет выполнено требуемое условие. Это займет как минимум nlog(n) времени сортировки.
Есть ли улучшения по сравнению с nlog(n) .
Можно считать, что все числа...
4967 просмотров
schedule
25.06.2023
Подсчитайте все подмножества массива, где наибольшее число является суммой оставшихся чисел
Я боролся с уровнем 3 испытания Греплина. Для тех, кто не в курсе, вот проблема:
вы должны найти все подмножества массива, где наибольшее число равно сумме остальных чисел. Например, для ввода:
(1, 2, 3, 4, 6)
подмножества будут
1 + 2 = 3...
2769 просмотров
schedule
08.12.2023
Быстрое решение суммы подмножества
Рассмотрим этот способ решения проблемы суммы подмножества:
def subset_summing_to_zero (activities):
subsets = {0: []}
for (activity, cost) in activities.iteritems():
old_subsets = subsets
subsets = {}
for (prev_sum, subset)...
14435 просмотров
schedule
19.05.2023
Сумма динамического программирования
Как бы вы использовали динамическое программирование, чтобы найти список положительных целых чисел в массиве, сумма которых ближе всего к некоторому положительному целому числу K, но не равна ему?
Я немного застрял, думая об этом.
2428 просмотров
schedule
08.03.2023
Рекурсия: понимание шаблона включения/исключения (суммы подмножества)
Мне нужно понять, как работает эта рекурсия, я понимаю простые примеры рекурсии, но более сложные примеры сложны. Даже несмотря на то, что у меня всего две строки кода, у меня возникла проблема... с самим оператором return . Я просто не понимаю,...
1016 просмотров
schedule
20.08.2022
Вариант PartitionProblem - фиксированный размер подмножеств
У меня есть проблема, которая является разновидностью проблемы с разделами, которая является NP-полной. Это проблема оптимизации, а не проблема принятия решения.
Задача : разбить список чисел на два подмножества так, чтобы разница их сумм была...
257 просмотров
schedule
08.04.2023
Haskell генерирует подмножества
У меня есть функция "подмножества", которая генерирует все подмножества данного набора:
subsets :: [Int] -> [[Int]]
subsets [] = [[]]
subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)
Как я могу объединить карту, foldl и фильтр в...
7666 просмотров
schedule
18.06.2022
Наименьшее число, которое не может быть образовано из суммы чисел из массива
Эту проблему мне задали в интервью Amazon -
Учитывая массив положительных целых чисел, вам нужно найти наименьшее положительное целое число, которое не может быть образовано из суммы чисел из массива.
Пример:
Array:[4 13 2 3 1]
result= 11 {...
16267 просмотров
schedule
08.03.2022
Вычисление минимального подмножества с заданной суммой
Я решал проблему в Scala, и это краткое изложение постановки задачи:
Есть список целых чисел (длины N, 0 ‹N‹ 10 ^ 5) и еще одно целое S (0 ‹S‹ 10 ^ 15). Вам необходимо найти минимальный размер минимального подмножества данного списка, сумма...
2189 просмотров
schedule
14.04.2023
Эффективный метод фильтрации и добавления на основе определенных условий (в данном случае 3 условий)
У меня есть кадр данных, который выглядит так
a b c d
1 1 1 0
1 1 1 200
1 1 1 300
1 1 2 0
1 1 2 600
1 2 3 0
1 2 3 100
1 2 3 200...
239 просмотров
schedule
23.06.2023
Сумма подмножества с двоичными числами
Я получил X двоичных чисел длины Y и хочу посмотреть, составляют ли они определенную сумму K.
Я провел небольшое исследование динамических решений для задач с суммой подмножеств; однако я думаю, что эта конкретная проблема представляет собой...
666 просмотров
schedule
19.07.2022
Правильно ли мое рекуррентное отношение для суммы подмножества?
Правильно ли это рекуррентное соотношение для задачи о сумме подмножеств? Утверждение: Выведите «Да» или «Нет» в зависимости от того, существует ли подмножество данного массива a [] , которое суммируется до заданного числа п .
dp [i] [j] =...
1303 просмотров
schedule
31.07.2023
Уменьшение времени выполнения для моей рекурсивной суммы подмножества algorthim
У меня есть рекурсивный алгоритм DFS, который правильно подсчитывает количество имеющихся подмножеств. Однако время выполнения этого метода абсурдно и чрезвычайно экспоненциально. Например, когда arr содержит набор ниже. Сумма, которую мы ищем,...
236 просмотров
schedule
19.08.2022
Common Lisp: использование (let) для вычисления рекурсивной функции
Поэтому я написал что-то, что возвращает максимальную сумму подмножества, учитывая список положительных целых чисел. Однако я хотел бы использовать (let), чтобы сделать код более эффективным. Я хотел бы знать, если и как это возможно.
(defun...
603 просмотров
schedule
28.10.2022
Сумма подмножества с плавающей запятой
Учтите, что у вас есть набор поплавков, например
4.2 ; 2.6 ; 6.9 ; 1.1
И вам нужно определить, существует ли Подмножество, сумма которого равна 5,3, и если да, то вернуть это множество.
Все заданные числа всегда имеют один десятичный...
1036 просмотров
schedule
18.10.2022
Алгоритмы - Динамическое программирование - Сумма подмножеств двух массивов
Моя домашняя работа включает вопрос о динамическом программировании:
Даны два массива натуральных чисел (a1, a2, ..., an и b1, b2, ..., bn), все они меньше n ^ 2, а также дано число B, которое меньше n ^ 3.
Вам нужно определить, есть ли...
892 просмотров
schedule
23.09.2022
неправильная сумма подмножества в O (n ^ 2)
Я знаю, что этот код / логика неверен для решения проблемы суммы подмножества, но не могу понять, почему.
Вычислите сумму всех возможных подмножеств и проверьте, равна ли какая-либо требуемая сумма. Это будет сделано за O (n ^ 2), что, очевидно,...
73 просмотров
schedule
29.08.2022
Сумма подмножества, сумма которого представляет собой огромное число с плавающей запятой
Я пытаюсь решить проблему суммы подмножества ( https://en.wikipedia.org/wiki/Subset_sum_problem или https://www.cs.cmu.edu/~ckingsf/class/02713-s13/lectures/lec15-subsetsum.pdf ).
Однако у меня есть особые условия. Набор S состоит из от одной...
442 просмотров
schedule
29.01.2023
Алгоритм поиска последовательной подпоследовательности, сумма которой будет запрошенным числом M из последовательности чисел в O (n)
Допустим, у нас есть массив положительных чисел, и нам дали значение M . Наша цель — найти, существует ли последовательная подпоследовательность в массиве положительных чисел, такая, что сумма последовательности точно равна сумме M. Если...
1669 просмотров
schedule
19.07.2022
