Задача о сумме подмножеств в общей формулировке звучит так:
Существует множество S чисел. Вопрос состоит в том, будет ли сумма некоторого подмножества от S равна заданному числу Т.
Известно, что данная задача NP-полная.
Мы будем решать эквивалентную задачу, где все числа являются натуральными.
Частным случаем задачи о сумме подмножеств является задача разбиения множества чисел:
Множество чисел S необходимо разбить на два подмножества S1 и S2, где сумма S1 равна сумме S2.
(От задачи о сумме подмножеств текущая отличается только тем, что T = Sum(S1) / 2 = Sum(S2) / 2)
Хочу предложить вам простой и элегантный способ относительно быстрого решения обеих задач методом целочисленного линейного программирования (ЦЛП). Мы получим не только точный ответ на вопрос, но и найдём искомое подмножество.
И так, у нас есть множество S натуральных чисел:
Нам необходимо ответить на вопрос: Возможно ли используя элементы данного множества получить сумму равную T?
Для нахождения ответа нужно решить линейное уравнение:
Если решение будет найдено, то ответ на вопрос положительный, если же решение невозможно, то отрицательный. Если решений несколько, нас устроит любое.
Используя Python и библиотеку PuLP, проиллюстрируем на примере.
import pulp as pl
src = [59, 63, 15, 43, 75, 72, 61, 48, 71, 55]
n = len(src)
# Искомое значение
val = sum(src) // 2
# Объявляем модель
model = pl.LpProblem(name="Subset sum problem", sense=pl.LpMinimize)
# Подключаем решатель CBC
solver = pl.PULP_CBC_CMD(msg=True)
# Объявляем переменные
x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]
# Целевая функция
model += pl.lpSum([x[i] for i in range(n)])
# Основное ограничение
model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val
print(model)В результате мы получим следующую модель решения линейного уравнения:
Subset sum problem:
MINIMIZE
1*x00000 + 1*x00001 + 1*x00002 + 1*x00003 + 1*x00004 + 1*x00005
+ 1*x00006 + 1*x00007 + 1*x00008 + 1*x00009 + 0
SUBJECT TO
_C1: 59 x00000 + 63 x00001 + 15 x00002 + 43 x00003 + 75 x00004 + 72 x00005
+ 61 x00006 + 48 x00007 + 71 x00008 + 55 x00009 = 281
VARIABLES
0 <= x00000 <= 1 Integer
0 <= x00001 <= 1 Integer
0 <= x00002 <= 1 Integer
0 <= x00003 <= 1 Integer
0 <= x00004 <= 1 Integer
0 <= x00005 <= 1 Integer
0 <= x00006 <= 1 Integer
0 <= x00007 <= 1 Integer
0 <= x00008 <= 1 Integer
0 <= x00009 <= 1 IntegerЗапускаем решатель и выводим решение
# Находим решение
status = model.solve(solver)
res = []
if status == 1:
for j, v in enumerate(model.variables()):
if v.value() > 0:
res.append(src[j])
print('Результат:', sum(res), res)
Результат: 281 [63, 75, 72, 71]Что и требовалось получить.
Однако, чем больше исходное множество и чем крупнее величины его составляющие, тем медленнее идёт поиск решения.
Например для поиска решения следующего списка из 24 элементов потребовалось порядка двадцати секунд.
source = [1485498, 1643002, 1391445, 1280110, 1145269, 1195187, 1908655, 1709512,
1006747, 1354760, 1527205, 1486247, 1941933, 1634072, 1084740, 1350249,
1581194, 1981871, 1646604, 1734106, 1042882, 1763564, 1397430, 1177643]Возможно ли как-то ускорить процесс нахождение решения?
Именно ответ на этот вопрос и побудил меня написать данный пост. Так как задача ЦЛП является NP-сложной, то считается что алгоритм, который находит решение является экспоненциальным от числа множеств.
Поэтому предлагаю "есть слона по кусочкам" (разбить сложную задачу на более простые и менее объемные части).
Мы разделим задачу на ряд задач меньшей сложности введением дополнительных ограничений в модель, вычислим их по отдельности. А затем выберем одно из допустимых решений, которое и будет считаться искомым.
Дополнительное ограничение для каждой из подзадач будет звучать следующим образом: Для нахождения искомого числа T нам понадобятся ровно Y множеств. Для каждой из подзадач мы будем брать значение Y из списка.
Y = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
Обратите внимание, как и в метафоре с батоном, решения по краям будут меньшего размера, потому находятся быстрее. Предлагаю начинать именно с краёв, так как найдя решение можно остановить поиск остальных возможных решений, экономя время.
Y = [1, 24, 2, 23, 3, 22, 4, 21, 5, 20, 6, 19, 7, 18, 8, 17, 9, 16, 10, 15, 11, 14, 12, 13]
Читать нужно следующим образом: Сумма значений любых Y элементов множества должна быть равна искомому T, где Y – значение из списка выше.
Решая подзадачи по такой схеме, мы найдём ответ быстрее, чем решая оригинальную задачу. Так например для нахождения решения для ряда выше, понадобится немногим более двух секунд.
Отличие от кода предыдущего решения будет только в том, что мы будем искать не одно решение, а несколько:
loop = list(range(1, n + 1))
loop = [loop.pop(0) if i % 2 == 0 else loop.pop(-1) for i in range(n)]
for val in loop:
# Устанавливаем дополнительное ограничение шага цикла
model.constraints['Y'] = pl.lpSum([x[j] for j in range(n)]) == val
print(model)
# Находим решение
status = model.solve(solver)
if status == 1:
res = []
for j, v in enumerate(model.variables()):
if v.value() > 0:
res.append(src[j])
return res
return []Таким образом мы последовательно будем строить ряд моделей и пытаться найти решение.
Subset sum problem:
MINIMIZE
1*x00000 + 1*x00001 + 1*x00002 + 1*x00003 + 1*x00004 + 1*x00005 + 1*x00006
+ 1*x00007 + 1*x00008 + 1*x00009 + 1*x00010 + 1*x00011 + 1*x00012 + 1*x00013
+ 1*x00014 + 1*x00015 + 1*x00016 + 1*x00017 + 1*x00018 + 1*x00019 + 1*x00020
+ 1*x00021 + 1*x00022 + 1*x00023 + 0
SUBJECT TO
_C1: 1485498 x00000 + 1643002 x00001 + 1391445 x00002 + 1280110 x00003
+ 1145269 x00004 + 1195187 x00005 + 1908655 x00006 + 1709512 x00007
+ 1006747 x00008 + 1354760 x00009 + 1527205 x00010 + 1486247 x00011
+ 1941933 x00012 + 1634072 x00013 + 1084740 x00014 + 1350249 x00015
+ 1581194 x00016 + 1981871 x00017 + 1646604 x00018 + 1734106 x00019
+ 1042882 x00020 + 1763564 x00021 + 1397430 x00022 + 1177643 x00023
= 17734962
Y: x00000 + x00001 + x00002 + x00003 + x00004 + x00005 + x00006 + x00007
+ x00008 + x00009 + x00010 + x00011 + x00012 + x00013 + x00014 + x00015
+ x00016 + x00017 + x00018 + x00019 + x00020 + x00021 + x00022 + x00023 = 1
VARIABLES
0 <= x00000 <= 1 Integer
0 <= x00001 <= 1 Integer
0 <= x00002 <= 1 Integer
0 <= x00003 <= 1 Integer
0 <= x00004 <= 1 Integer
0 <= x00005 <= 1 Integer
0 <= x00006 <= 1 Integer
0 <= x00007 <= 1 Integer
0 <= x00008 <= 1 Integer
0 <= x00009 <= 1 Integer
0 <= x00010 <= 1 Integer
0 <= x00011 <= 1 Integer
0 <= x00012 <= 1 Integer
0 <= x00013 <= 1 Integer
0 <= x00014 <= 1 Integer
0 <= x00015 <= 1 Integer
0 <= x00016 <= 1 Integer
0 <= x00017 <= 1 Integer
0 <= x00018 <= 1 Integer
0 <= x00019 <= 1 Integer
0 <= x00020 <= 1 Integer
0 <= x00021 <= 1 Integer
0 <= x00022 <= 1 Integer
0 <= x00023 <= 1 IntegerОтличаться они будут только значением правой части равенства в 18 строке.
Подход описанный в работе хоть и не идеальный, но вполне рабочий. Несмотря на то, что сама задача NP-сложна, мы можем находить решение для множеств от нескольких десятков до нескольких сотен элементов в зависимости от исходных данных.
Примечание
Отдельно стоит отметить, что не каждый решатель целочисленных линейных уравнений способен точно решить целочисленную линейную задачу. Из-за особенностей реализации многие решатели присутствующие на рынке имеют некоторую погрешность вычислений, которая незначительно влияет на конечный результат в типовых задачах. Но в данном алгоритме, раз уж мы говорим про точное решение, особенно при больших значениях входных данных, выбор решателя может катастрофически повлиять на результат.
В моих тестах только CBC от COIN-OR Foundation и OR-Tools от Google, справились с данной задачей верно.
Заключение:
Некоторые задачи целочисленного линейного программирования можно решать более быстро, если разбить их ряд более простых задач путём ввода дополнительных ограничений.
Спасибо за внимание!
Полный код
import pulp as pl
import random as rnd
from datetime import datetime
# ==========================================================================
def ssp(src: list, val: int):
"""
Задача о сумме подмножеств натуральных чисел (Subset sum problem - SSP)
"""
n = len(src)
# Объявляем модель
model = pl.LpProblem(name="ssp", sense=pl.LpMinimize)
# Подключаем решатель CBC
solver = pl.PULP_CBC_CMD(msg=True)
# Объявляем переменные
x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]
# Целевая функция
model += pl.lpSum([x[i] for i in range(n)])
# Основное ограничение
model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val
# Находим решение
status = model.solve(solver)
if status == 1:
s = []
for j, v in enumerate(model.variables()):
if round(v.value()) > 0:
s.append(src[j])
return s
return []
# ==========================================================================
def ssp_optimized(src: list, val: int):
"""
Задача о сумме подмножеств натуральных чисел оптимизированный алгоритм
(Subset sum problem optimized - SSP)
"""
n = len(src)
# Объявляем модель
model = pl.LpProblem(name="ssp", sense=pl.LpMinimize)
# Подключаем решатель CBC
solver = pl.PULP_CBC_CMD(msg=True)
# Объявляем переменные
x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]
# Целевая функция
model += pl.lpSum([x[i] for i in range(n)])
# Основное ограничение
model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val
loop = list(range(1, n + 1))
loop = [loop.pop(0) if i % 2 == 0 else loop.pop(-1) for i in range(n)]
for val in loop:
# Устанавливаем дополнительное ограничение шага цикла
model.constraints['Y'] = pl.lpSum([x[j] for j in range(n)]) == val
# Находим решение
status = model.solve(solver)
if status == 1:
s = []
for j, v in enumerate(model.variables()):
if round(v.value()) > 0:
s.append(src[j])
return s
return []
# ==========================================================================
n = 23
rnd.seed(0)
# Генерируем случайный ряд чисел
src = [rnd.randint(1000000, 2000000) for i in range(n)]
t = sum(src) // 2
print(f'source = {src}')
print()
start_time = datetime.now()
res = ssp(src, t)
date_diff = (datetime.now() - start_time).total_seconds()
print('solution =', res)
print('time =', date_diff)
print()
start_time = datetime.now()
res = ssp_optimized(src, t)
date_diff = (datetime.now() - start_time).total_seconds()
print('solution optimized =', res)
print('time =', date_diff)Комментарии (39)
wataru
12.04.2024 08:48Есть же решение через динамическое программирование за O(N sum). Надо завести массив размером с искоммую сумму, и там помечать те суммы, которые можно получить. Там же можно хранить, какой элемент множества можно взять.
Для вот таких вот чисел в задаче оно найдет решение за доли секунды. Сумма порядка 10 миллионов. С другой стороны, для 24 чисел можно полным перебором перебрать ~8 миллионов вариантов (2^24), что будет даже быстрее.
Имеет смысл применять что-то иное, вроде линейного программирования, когда у вас числа большие и их самих больше. Как долго ваше решение работает, если чисел 50, а сумма их - порядка миллиарда?
rebuilder Автор
12.04.2024 08:48Динамическое программирование требует очень много память на больших N и P. Линейное в этом смысле сильно выигрывает, но у него плохо со стабильностью результатов, уже больно оно зависит от набора входных данных. На некоторых наборах выигрыш феноменален, не некоторых экспонента всё портит. Но по моим наблюдениям в среднем разы рвёт ДП.
На случайных наборах результат очень хороший, особенно когда допустимых решений много.
Если вы приложите набор тестовых данных, то могу протестировать.
wataru
12.04.2024 08:48+1Динамическое программирование требует очень много память на больших N и P.
Нет, от N оно линейно. ДП страдает, когда числа большие. А когда N маленькое - отлично работает полный перебор.
Вот и получается, что единственная ниша, где ваш метод может побороться - это относительно большое (>=30) количество больших (~миллиард) чисел. Есть ли там выигрыш?
rebuilder Автор
12.04.2024 08:48+1Выигрыш есть, именно для этого пост и писался. Только что бы это показать нужно смотреть на практике. Выигрыш очень велик, когда количество чисел превалирует над размером.
n = 100 val = 77019193 source = [1885440, 1403958, 1794772, 1933488, 1441001, 1042450, 1271493, 1536110, 1509532, 1424604, 1962838, 1821872, 1870163, 1318046, 1499748, 1375441, 1611720, 1934973, 1952225, 1229053, 1529202, 1146039, 1295528, 1146534, 1792518, 1099437, 1648406, 1838234, 1262674, 1953938, 1558433, 1739426, 1849574, 1631140, 1945989, 1154100, 1325213, 1103560, 1765284, 1077324, 1942500, 1891786, 1717209, 1346236, 1495077, 1587007, 1105592, 1370977, 1455262, 1331556, 1640561, 1671532, 1957361, 1214410, 1579363, 1500181, 1464197, 1907343, 1546678, 1273145, 1065304, 1844132, 1963080, 1575352, 1960489, 1014723, 1097802, 1754665, 1880899, 1418196, 1744754, 1864912, 1823182, 1700609, 1655638, 1001198, 1641620, 1517553, 1868287, 1909747, 1349317, 1255759, 1765752, 1341001, 1737822, 1912755, 1066043, 1200348, 1961564, 1595078, 1232473, 1250206, 1842368, 1149416, 1842194, 1569366, 1469730, 1095646, 1084353, 1335601] solution optimized = [1794772, 1933488, 1536110, 1509532, 1962838, 1821872, 1870163, 1611720, 1934973, 1952225, 1792518, 1648406, 1838234, 1953938, 1558433, 1631140, 1945989, 1942500, 1891786, 1717209, 1640561, 1671532, 1957361, 1579363, 1907343, 1546678, 1844132, 1963080, 1960489, 1880899, 1864912, 1823182, 1700609, 1641620, 1517553, 1868287, 1909747, 1765752, 1912755, 1961564, 1842368, 1842194, 1569366] time = 4.474821
qw1
12.04.2024 08:48Видимо, линейная алгебра сильно продвинулась из-за развития ML.
Потому что, если решать в лоб, "по-школьному", дискриминант матрицы на 30 строк из таких больших чисел переполнит любые фиксированные типы. И ещё проблема, что решение должно быть точным, а любая микро-погрешность не найдёт решение Xi in {0,1}, посчитается какой-нибудь Xi=0.99999 и всё, вариант отсечётся. То есть, я думаю, тщательное тестирование на очень сложных случаях покажет, что этот метод не всегда даёт правильный результат.
wataru
12.04.2024 08:48Тут не линейная алгебра же. Это же целочисленное программирование.
qw1
12.04.2024 08:48Очень интересно. Я вообще не знал, что есть такое направление. Есть ли учебники, или это всё на уровне исследований?
wataru
12.04.2024 08:48+1Есть учебники. Это весьма зрелая область. Первое, что нагуглил. Вообще, начинают изучение не с целочисленного, а с простого линейного программирования. Симплекс методу из этой области уже лет 70. В целочисленных решателях часто используют итеративный подход со всякими отсеченями, что есть в общем-то надстройка над этим.
qw1
12.04.2024 08:48Симплекс-метод это старая тема, которую в ВУЗах дают даже не математикам. А вот в целочисленной области что придумали, это интересно.
wataru
12.04.2024 08:48Смутно помню метод, который запускает симплекс, получает нецелочисленное решение, добавляет ограничение, которое отсекает вот этот лишний оптимум. И так далее, пока не найдется целое решение. Вроде это оно. Ему лет 60. Что там нового в этой теме напридумывали - не в курсе.
qw1
12.04.2024 08:48Этот алгоритм это есть в книжке, которую вы привели выше.
Но там те проблемы, которые я упомянул - требуется работа в поле рациональных чисел с большими знаменателями.
Там дальше в книжке рассмотрен алгоритм, работающий только в целых числах, пока я ещё не докурил, свободен ли он от этих проблем.
rebuilder Автор
12.04.2024 08:48И ещё проблема, что решение должно быть точным, а любая микро-погрешность не найдёт решение Xi in {0,1}, посчитается какой-нибудь Xi=0.99999 и всё, вариант отсечётся. То есть, я думаю, тщательное тестирование на очень сложных случаях покажет, что этот метод не всегда даёт правильный результат.
Это зависит от качества решателя. Если под капотом используются float64, так и бывает у большинства решателей.
Однако, как я считаю хороший решатель должен работать с натуральными дробями, и тогда погрешность не возникает совсем.
wataru
12.04.2024 08:48А динамическое программирование запускали? Сколько оно работает?
rebuilder Автор
12.04.2024 08:48ДП больше пары десятков элементов у меня не тянет. Тот алгоритм что я использовал сжирает всю память для кэша.
Возможно алгоритм что не хранит всё кэше и вывезет. Но если предположить, что по скорости алгоритм с меморизацией и без равны, то навряд ли сравняется с ЛП.
wataru
12.04.2024 08:48Да, вы какой-то странный алгоритм реализовали. Или numpy не использовали, без него массив 77М*100 очень много памяти занимает. Код ниже на вашем тесте отработал за 1.6 секунд. Запустите на вашей машине, чтобы сравнить.
import numpy as np import time def find_subset_sum(numbers, target): """ Finds a subset of given numbers that sums up to the target using dynamic programming. :param numbers: List of integers :param target: Target sum :return: Subset of numbers that adds up to the target (or None if not possible) """ n = len(numbers) dp = np.zeros(target + 1, dtype=bool) dp[0] = True for i in range(1, n + 1): dp |= np.roll(dp, numbers[i - 1]) if not dp[target]: return None subset = [] j = target for i in range(n, 0, -1): if j >= numbers[i - 1] and dp[j - numbers[i - 1]]: subset.append(numbers[i - 1]) j -= numbers[i - 1] return subset[::-1] target_sum = 77019193 source = [1885440, 1403958, 1794772, 1933488, 1441001, 1042450, 1271493, 1536110, 1509532, 1424604, 1962838, 1821872, 1870163, 1318046, 1499748, 1375441, 1611720, 1934973, 1952225, 1229053, 1529202, 1146039, 1295528, 1146534, 1792518, 1099437, 1648406, 1838234, 1262674, 1953938, 1558433, 1739426, 1849574, 1631140, 1945989, 1154100, 1325213, 1103560, 1765284, 1077324, 1942500, 1891786, 1717209, 1346236, 1495077, 1587007, 1105592, 1370977, 1455262, 1331556, 1640561, 1671532, 1957361, 1214410, 1579363, 1500181, 1464197, 1907343, 1546678, 1273145, 1065304, 1844132, 1963080, 1575352, 1960489, 1014723, 1097802, 1754665, 1880899, 1418196, 1744754, 1864912, 1823182, 1700609, 1655638, 1001198, 1641620, 1517553, 1868287, 1909747, 1349317, 1255759, 1765752, 1341001, 1737822, 1912755, 1066043, 1200348, 1961564, 1595078, 1232473, 1250206, 1842368, 1149416, 1842194, 1569366, 1469730, 1095646, 1084353, 1335601] start = time.time() result = find_subset_sum(source, target_sum) end = time.time() elapsed_time = end - start print(f"Execution time: {elapsed_time:.6f} seconds") print(f"Subset with sum {target_sum}: {result}")Можно извратиться с битовыми оптимизациями и раз в 30 ускорить.
rebuilder Автор
12.04.2024 08:48Алгоритм ДП, что я рассматривал, очень неэффективен по сравнению с тем, что предоставили Вы.
Беру свои слова назад, в такой реализации ДП на многих наборах обходит мою версию ЛП.
Любопытно, на некоторых наборах сильно лидирует ЛП, но если проигрывает, то часто значительно, тогда как ДП более стабилен. Как вариант интересно устраивать гонку алгоритмов, какой финиширует первым.
Однако меня огорчил тот факт, что на больших наборах входных данных, памяти ДП всё же не хватает, и он не выполняется с ошибкой:
MemoryError: Unable to allocate 14.2 GiB for an array with shape (15207959671,) and data type bool.
n = 200 t = 15207959670 source = [118034063, 176397250, 108470054, 134234785, 115826780, 166496171, 160329669, 163383683, 187455328, 150951092, 128179657, 112597620, 165479012, 103804733, 152319252, 158085012, 181528947, 100282669, 193393106, 159778857, 135746282, 196843463, 130703945, 179343270, 113720696, 142604684, 104105718, 102996023, 103415285, 187180606, 172667152, 101235465, 151164366, 192138303, 129071478, 156655527, 197422287, 103897788, 170817221, 129754951, 158772277, 166546792, 174203556, 131284065, 146399124, 130986382, 190845073, 129364293, 161686932, 138893829, 102884299, 155858725, 174686034, 186207290, 113421809, 124951916, 184470316, 197125183, 139780845, 116225575, 199743456, 144653591, 196835997, 195454543, 167216197, 156654242, 168144655, 189966890, 125481199, 140717432, 138139224, 178863733, 167023240, 167818046, 152795029, 179054544, 104633978, 164454973, 132580007, 199821838, 154262629, 155608283, 189220365, 123220660, 149274526, 173658522, 194360533, 190527955, 199081602, 150291788, 111605483, 158916432, 189088064, 168239848, 114486288, 121971213, 169919170, 152781805, 149730710, 165725551, 198350162, 103969484, 162991083, 105836765, 141410118, 194406345, 182518497, 179615772, 177601456, 152828055, 186859830, 122863882, 122628343, 167409318, 130459014, 101651090, 126778633, 172426227, 173596743, 131162152, 154285013, 168957265, 146147529, 177550306, 147415655, 161623617, 136142079, 188478314, 173550819, 181731190, 197898435, 100766266, 151497950, 199388685, 168786576, 117347564, 169615820, 175344177, 127579764, 157188922, 107532741, 164572392, 148954043, 176504015, 174410468, 126821992, 167742434, 155485614, 165085546, 147887538, 155623117, 146449792, 100212701, 172273400, 172492277, 183683337, 182201978, 144444516, 161491422, 180511200, 103754738, 130817065, 185278064, 123784892, 173921254, 178445010, 124264416, 112294532, 173957878, 134264986, 104356590, 190343768, 109456105, 111171496, 102240178, 160800468, 101954206, 137741579, 133495272, 136056483, 114695314, 183859516, 124777959, 146227654, 138961302, 109330196, 122477484, 121424575, 134254527, 170783798, 122568032, 188134944, 136629955, 187000307, 195507983, 139526151, 161029019, 194304805, 143218345, 166638250] solution optimized = [176397250, 166496171, 160329669, 163383683, 187455328, 165479012, 181528947, 193393106, 159778857, 179343270, 187180606, 172667152, 192138303, 197422287, 170817221, 166546792, 174203556, 190845073, 161686932, 174686034, 186207290, 184470316, 197125183, 199743456, 196835997, 195454543, 167216197, 189966890, 178863733, 167023240, 179054544, 164454973, 199821838, 189220365, 173658522, 194360533, 190527955, 199081602, 158916432, 189088064, 169919170, 165725551, 198350162, 194406345, 182518497, 179615772, 177601456, 186859830, 167409318, 172426227, 173596743, 168957265, 177550306, 188478314, 173550819, 181731190, 197898435, 199388685, 168786576, 169615820, 175344177, 164572392, 176504015, 174410468, 155485614, 172273400, 172492277, 183683337, 182201978, 180511200, 185278064, 173921254, 178445010, 173957878, 190343768, 160800468, 183859516, 170783798, 188134944, 187000307, 195507983, 161029019, 194304805, 143218345, 166638250]wataru
12.04.2024 08:48Да, я про это ограничение и писал. Если числа большие, то ДП вообще не работает. Но вот вопрос в том, хорошо ли в этом случае работает линейный решатель?
rebuilder Автор
12.04.2024 08:48Не утверждаю, что решение с ЦЛП - серебряная пуля.
Возможно, решение находится не всегда быстро, но по памяти более гуманно факт.
qw1
12.04.2024 08:48Цикл 70млн*100 итераций, который имеет примерно такой же футпринт по памяти, работает 4516 ms на моей машине.
qw1
12.04.2024 08:48Динамическое программирование требует очень много память на больших N и P
Нет, в этой задаче таблица заполняется сверху вниз, и нужно хранить только последнюю заполненную строку для расчёта следующей.
wataru
12.04.2024 08:48Там все сложно с восстановлением ответа. Если вам надо знать только есть ли разбиение, то такая оптимизация отлично работает. А если надо само подмножество вывести, то все совсем плохо. Ибо вы не знаете, какие числа вам понадобятся потом и какие были использованы ранее. Так что во время восстановления можно прийти в ситуацию, что вычтя какое-то число вы оказываетесь в сумме, которую набрать нельзя. Ну, или вы одно и то же число несколько раз возьмете.
wataru
12.04.2024 08:48Вообще, придумалось как хранить только одну строку, но там есть хитрость:
vector<int> SubsetSum(const vector<int> &numbers, int target) vector<int> dp(target+1); dp[0] = 1; for (auto number in numbers) { for (int j = target; j >= number; --j) { if (dp[j] == 0 && dp[j-number] != 0) dp[j] = number; } } vector<int> answer; if (dp[target] == 0) return answer; while (target > 0) { answer.push_back(target); cur_sum -= dp[target]; } return answer; }Идея в том, что бы обновлять только те позиции, которые нельзя было собрать на предыдущем шаге. И в каждой ячейке хранить последнее взятое число. Таким образом каждая ячейка ведет на состояние, которое можно получить только более ранними числами и последнее взятое число там нигде не встречается никогда.
Проблема только, что в питоне это дико тормозит из-за его ужастных циклов/массивов. Изврат с numpy тоже не очень быстр из-за постоянных аллокаций.qw1
12.04.2024 08:48Видимо, где-то ошибка. Последний цикл бесконечный, потому что условие выхода target не обновляется. А cur_sum вообще не объявлен, наверное он и есть target. Вообще, интересная идея идти от конца к началу, чтобы не хранить "новую" и "предыдущую" строку, меняя их местами, а считать, что "новая" - справа, предыдущая - слева от итератора.
qw1
12.04.2024 08:48Можно ускорить где-то в 2 раза, если заполнять только "диагональ", а числа будут отсортированы
max_filled = 0; for (auto number in numbers) { for (int j = min(target, max_filled+number); j >= number; --j) { if (dp[j] == 0 && dp[j-number] != 0) dp[j] = number, max_filled = max(max_filled, j);wataru
12.04.2024 08:48Да, действительно. Можно не перебирать слишком большие j, ведь больше суммы текущих чисел все-равно собрать мы никак не сможем.
SemenovVV
в вашей ссылке на вики https://ru.wikipedia.org/wiki/Задача_о_сумме_подмножеств
написано :
обратите внимание на Замечание: здесь буквы N и P не имеют ничего общего с классом задач NP.
rebuilder Автор
Вы правы. Мне не хотелось излишне усложнять текст.
Так как для чисел порядка миллиарда, число двоичных разрядов практически не имеет значения, то я несколько упростил повествование.
wataru
Эта задача действительно NP-полная.
rebuilder Автор
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
wataru
Мне показалось, что SemenovVV увидел по ссылке N, P и подумал, что вы ошибочно интерпретировали их как NP. Другого прочтения этого комментария я придумать не могу.
qw1
Только в действительных числах, а такого в CS не бывает.
Для натуральных чисел (можно обобщить и для рациональных), сложность решения M*N, где N - число элементов, M - сумма элементов множества.
https://leetcode.com/discuss/study-guide/1152328/01-Knapsack-Problem-and-Dynamic-Programming
wataru
Но в общем случае M = O(2^N). Ведь в CS сложность считается от размера входных данных. И если у вас одно число на N бит, то вот у вас уже M=2^N. Если же вводить ограничения на числа, то это уже немного другая задача. Но все-равно, если там 64-битные числа, то этот метод не применим, ибо массива на 10^18 элементов вы не заведете. Да и если заведете, работать это будет не сильно быстро.
qw1
Да, точно. Я всё время забываю, что есть быдлокодерская сложность, где каждое сложение-умножение это O(1), а цикл
for i=1 to Nимеет сложность O(N), и есть сложность для адептов Машин Тьюринга, где тот же цикл - уже NP-полная задача, потому что число итераций растёт как степень двойки от длины входа.wataru
Ну смотрите, задача разложения числа на множители тоже решается одним циклом. Перебрали все числа до корня - поделили. Даже не за линию, а за O(Sqrt(N)). Сублинейный алгоритм! Но вы же не будете спорить, что задача факторизации - NP-полная? Или вся криптограия идет лесом.
Вот тут тоже самое же.
qw1
Я и говорю, что есть две параллельные терминологии.
Часто, говоря о сложности задачи, считают её не от длины записи, а от значения входа.
Какая сложность поиска элмемента в массиве длины N?
O(N)
Какая сложность наивной факторизации числа N?
O(N^2).
wataru
Нет. Терминология одна. У вас непонимание, что такое NP и его братья.
Вернемся к началу дисскуссии:
Я написал, что задача NP-полная, вы возразили, что есть решение за O(NM). Вообще, определения там запутанные, так что давайте посмотрим на определение P-задач:
Вот эти NP-полные - это те, для которых неизвестны "быстрые" алгоритмы, и их скорее всего их не существутет, потому что решение для любой такой задачи автоматически "быстро" решает их все. Обратите внимание на выделенные жирным слова в определении. Надо считать ассмтотику относительно размера входных данных. Эти N, M для ДП - не размер входных данных. Собственно, M будет экспоненциально от этого размера.
С практической точки зрения, вы можете на основе этой задачи сделать шифр, где публичный ключ - множество, а приватный - подмножество с заданной суммой. И жалкий 4096-битный ключ вам этим ДП придется взламывать тысячи лет. Хотя для действительно полиномиальных задач любой 4-килобайтный входной файлик будет пережеван весьма быстро.
Так что задача все еще остается "сложной" и она действительно является NP-полной.