Ну вот новый контрпример: ([2, 3, 3, 4, 52, 52, 100, 1000, 1000], 108) ...
Ну вот я добавил пару 1000 в массив и ваша эвристика сломалась.
Где же сломалась? Работает, проверьте исходные данные.
Еще раз, проблема в том, что можно получить ситуацию, что вам надо набрать 8, а у вас остались числа [2, 3, 3, 4]
Я понимаю резон в ваших словах, но и вы поймите, что смысл всех танцев как раз в том, чтобы исключить возможность выбора тех величин, что приведут к тупику в дальнейшем.
И да вы правы нужно доказать логически, а это не простая задача.
Благодарю Вас в вашем упорстве находить истину и желании помочь другим в этом же.
Действительно в моих первоначальных рассуждениях закралась ошибка: Если мы усекаем список просматриваемых чисел на первом этапе, то его и на втором этапе нужно усекать в том же объёме.
Однако, это не отменяет работоспособность самой идеи получения списка результата. Сортировка по возрастанию как раз и используется для того чтобы числа, которые могут состоять из нескольких меньших чисел утилизировались в первую очередь.
Я не убеждён, что и новый алгоритм не может содержать ошибки, но вы так категорично утверждаете, что решение в корне не верно, что вызывает желание понять почему.
На мой взгляд так как сложение - операция коммуникативная и ассоциативная, мы выстраиваем поле в рамках которого ищем результат, и не важно в каком порядке мы будем обходить это поле решений.
И ещё в процессе нашей дискуссии я исправил огрех, который не заметил сразу, после рола правые биты оказываются слева строки, а это иногда вносит ошибку. Потому выкладываю очередную версию, в которой все ваши контрпримеры вычисляются верно.
import bitstring as bit
def find_subset_sum(numbers: list, target: int):
numbers.sort()
dp = bit.BitArray(target + 1)
dp[0] = 1
count = -1
for i in numbers:
temp = dp.copy()
dp.ror(i)
dp.set(0, range(i))
dp |= temp
print('i:', i, dp.bin)
count += 1
if dp[target] == 1:
break
if not dp[target]:
return []
print()
subset = []
j = target
for i in numbers[count::-1]:
if j >= i and dp[j - i]:
print('i:', i, 'j:', j, '- берём')
subset.append(i)
j -= i
else:
print('i:', i, 'j:', j, '- не берём')
return subset[::-1]
source = [2, 3, 3, 4, 52, 52, 100]
target_sum = 108
print('source:', source)
print('target_sum:', target_sum)
print()
result = find_subset_sum(source, target_sum)
print('result:', sum(result), result)
Вам надо набрать 8, есть числа {2,3,3,4}. Первым шагом вы возьмете 4, ведь можно же набрать 4 всеми этими числами. И дальше все. Оставшиеся 4 вы никак из {2,3,3} не наберете.
Немного доработал представленный алгоритм динамического программирования для Python.
Теперь он требует в восемь рез меньше памяти и в два раза быстрее, чем через numpy. Но это ожидаемо, так как используется более плотное хранение бит благодаря модулю bitstring.
Ещё мне показалось уместным не дожидаться обхода всего входного массива, если допустимое решение уже найдено, что даёт приличный прирост производительности.
Возможно, кому то пригодится.
import bitstring as bit
import random as rnd
import time
def find_subset_sum(numbers: list, target: int):
dp = bit.BitArray(target + 1)
dp[0] = 1
for i in numbers:
temp = dp.copy()
dp.ror(i)
dp |= temp
if dp[target] == 1:
break
if not dp[target]:
return []
subset = []
j = target
for i in numbers[::-1]:
if j >= i and dp[j - i]:
subset.append(i)
j -= i
return subset[::-1]
n = 100
# rnd.seed(0)
source = [rnd.randint(1000000, 9999999) for i in range(n)]
print('source:', source)
target_sum = sum(source) // 2
print('target_sum:', target_sum)
print()
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}")
Алгоритм ДП, что я рассматривал, очень неэффективен по сравнению с тем, что предоставили Вы.
Беру свои слова назад, в такой реализации ДП на многих наборах обходит мою версию ЛП.
Любопытно, на некоторых наборах сильно лидирует ЛП, но если проигрывает, то часто значительно, тогда как ДП более стабилен. Как вариант интересно устраивать гонку алгоритмов, какой финиширует первым.
Однако меня огорчил тот факт, что на больших наборах входных данных, памяти ДП всё же не хватает, и он не выполняется с ошибкой:
MemoryError: Unable to allocate 14.2 GiB for an array with shape (15207959671,) and data type bool.
И ещё проблема, что решение должно быть точным, а любая микро-погрешность не найдёт решение Xi in {0,1}, посчитается какой-нибудь Xi=0.99999 и всё, вариант отсечётся. То есть, я думаю, тщательное тестирование на очень сложных случаях покажет, что этот метод не всегда даёт правильный результат.
Это зависит от качества решателя. Если под капотом используются float64, так и бывает у большинства решателей.
Однако, как я считаю хороший решатель должен работать с натуральными дробями, и тогда погрешность не возникает совсем.
ДП больше пары десятков элементов у меня не тянет. Тот алгоритм что я использовал сжирает всю память для кэша.
Возможно алгоритм что не хранит всё кэше и вывезет. Но если предположить, что по скорости алгоритм с меморизацией и без равны, то навряд ли сравняется с ЛП.
Выигрыш есть, именно для этого пост и писался. Только что бы это показать нужно смотреть на практике. Выигрыш очень велик, когда количество чисел превалирует над размером.
Динамическое программирование требует очень много память на больших N и P. Линейное в этом смысле сильно выигрывает, но у него плохо со стабильностью результатов, уже больно оно зависит от набора входных данных. На некоторых наборах выигрыш феноменален, не некоторых экспонента всё портит. Но по моим наблюдениям в среднем разы рвёт ДП.
На случайных наборах результат очень хороший, особенно когда допустимых решений много.
Если вы приложите набор тестовых данных, то могу протестировать.
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
Где же сломалась? Работает, проверьте исходные данные.
Я понимаю резон в ваших словах, но и вы поймите, что смысл всех танцев как раз в том, чтобы исключить возможность выбора тех величин, что приведут к тупику в дальнейшем.
И да вы правы нужно доказать логически, а это не простая задача.
Благодарю Вас в вашем упорстве находить истину и желании помочь другим в этом же.
Действительно в моих первоначальных рассуждениях закралась ошибка: Если мы усекаем список просматриваемых чисел на первом этапе, то его и на втором этапе нужно усекать в том же объёме.
Однако, это не отменяет работоспособность самой идеи получения списка результата. Сортировка по возрастанию как раз и используется для того чтобы числа, которые могут состоять из нескольких меньших чисел утилизировались в первую очередь.
Я не убеждён, что и новый алгоритм не может содержать ошибки, но вы так категорично утверждаете, что решение в корне не верно, что вызывает желание понять почему.
На мой взгляд так как сложение - операция коммуникативная и ассоциативная, мы выстраиваем поле в рамках которого ищем результат, и не важно в каком порядке мы будем обходить это поле решений.
И ещё в процессе нашей дискуссии я исправил огрех, который не заметил сразу, после рола правые биты оказываются слева строки, а это иногда вносит ошибку. Потому выкладываю очередную версию, в которой все ваши контрпримеры вычисляются верно.
Обратите внимание на условие:
Оно заранее завершает процесс заполнения dp, и исключает во многом те ситуации, что вы описывали в предыдущем ответе.
Это не так! Проиллюстрирую:
Так понимаю достаточно сделать:
numbers.sort()
первым шагом функции.Поскольку обход цикла идёт с конца списка, проблема полностью устраняется.
Могли бы вы подробнее пояснить, что за идея у вас тут оформлена. Очень хотелось бы разобраться, но боюсь мой скил в плюсах не настолько хорош.
Немного доработал представленный алгоритм динамического программирования для Python.
Теперь он требует в восемь рез меньше памяти и в два раза быстрее, чем через numpy. Но это ожидаемо, так как используется более плотное хранение бит благодаря модулю bitstring.
Ещё мне показалось уместным не дожидаться обхода всего входного массива, если допустимое решение уже найдено, что даёт приличный прирост производительности.
Возможно, кому то пригодится.
Не утверждаю, что решение с ЦЛП - серебряная пуля.
Возможно, решение находится не всегда быстро, но по памяти более гуманно факт.
Алгоритм ДП, что я рассматривал, очень неэффективен по сравнению с тем, что предоставили Вы.
Беру свои слова назад, в такой реализации ДП на многих наборах обходит мою версию ЛП.
Любопытно, на некоторых наборах сильно лидирует ЛП, но если проигрывает, то часто значительно, тогда как ДП более стабилен. Как вариант интересно устраивать гонку алгоритмов, какой финиширует первым.
Однако меня огорчил тот факт, что на больших наборах входных данных, памяти ДП всё же не хватает, и он не выполняется с ошибкой:
MemoryError: Unable to allocate 14.2 GiB for an array with shape (15207959671,) and data type bool.
Это зависит от качества решателя. Если под капотом используются float64, так и бывает у большинства решателей.
Однако, как я считаю хороший решатель должен работать с натуральными дробями, и тогда погрешность не возникает совсем.
ДП больше пары десятков элементов у меня не тянет. Тот алгоритм что я использовал сжирает всю память для кэша.
Возможно алгоритм что не хранит всё кэше и вывезет. Но если предположить, что по скорости алгоритм с меморизацией и без равны, то навряд ли сравняется с ЛП.
Выигрыш есть, именно для этого пост и писался. Только что бы это показать нужно смотреть на практике. Выигрыш очень велик, когда количество чисел превалирует над размером.
Динамическое программирование требует очень много память на больших N и P. Линейное в этом смысле сильно выигрывает, но у него плохо со стабильностью результатов, уже больно оно зависит от набора входных данных. На некоторых наборах выигрыш феноменален, не некоторых экспонента всё портит. Но по моим наблюдениям в среднем разы рвёт ДП.
На случайных наборах результат очень хороший, особенно когда допустимых решений много.
Если вы приложите набор тестовых данных, то могу протестировать.
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
Вы правы. Мне не хотелось излишне усложнять текст.
Так как для чисел порядка миллиарда, число двоичных разрядов практически не имеет значения, то я несколько упростил повествование.
Скорее забэкапить крайний дамп... в облако?
Да, это эпичный феил! На простых кейсах такого не наблюдалось, а вот когда точки как забор и легли улиткой.
Спасибо! Осознал, признаю ошибку! Вам + в карму, буду думать. Хорошие кейсы.
обводил по точкам.