Я боролся с этой проблемой, как и все остальные, и я совершенно уверен, что было более чем достаточно сообщений, объясняющих эту проблему. Однако с точки зрения полного понимания этого я хотел поделиться своими мыслями и получить более эффективные решения от всех замечательных людей, связанных с проблемой Subset Sum.
Я искал его в Интернете, и на самом деле есть много источников, но я действительно готов повторно реализовать алгоритм или найти свой собственный, чтобы полностью понять.
Главное, с чем я борюсь, — это эффективность, учитывая, что размер набора будет большим. (У меня нет предела, просто концептуально большой). Две фазы, которые я пытаюсь реализовать, это поиск двух чисел, равных заданному целому числу T, поиск трех чисел и, наконец, < b>К чисел. Некоторые идеи у меня есть;
Для двух целочисленных частей я в основном сортирую массив O(nlogn) и для каждого элемента в массиве ищу его отрицательное значение. (т. е. если элемент массива 3 ищет -3). Может быть, включение хэш-таблицы могло бы быть лучше, обеспечивая O(1) индексацию элемента?
Для трех или более целых чисел я нашел замечательный пост в блоге: http://www.skorks.com/2011/02/algorithms-a-dropbox-challenge-and-dynamic-programming/ . Однако даже сам автор утверждает, что для больших чисел это неприменимо.
Поэтому я интересовался 2 и 3 и более целыми числами, какие идеи можно применить для решения проблемы подмножества. Я изо всех сил пытаюсь настроить метод динамического программирования, который будет эффективен и для больших входных данных.
