Найдите наиболее распространенную сумму (суммы) в списке целых чисел
Я пытаюсь найти наиболее распространенную сумму в списке целых чисел.
Например, учитывая список 2,4,6,8, наиболее распространенными суммами являются 10, 12 и 14, так как все они могут быть составлены двумя способами:
2 + 8 = 4 + 6 = 10
2 + 4 + 6 = 4 + 8 = 12
2 + 4 + 8 = 6 + 8 = 14
Конечно, другие возможные суммы встречаются только один раз. Я знаю, что простой список, подобный этому, может быть обработан методом перебора, но мне нужен какой-то общий намек на то, как я могу решить эту проблему для больших списков. Например, возможно, я могу как-то использовать динамическое программирование?
Технически вам придется проверять каждое подмножество, чтобы узнать наиболее часто встречающиеся суммы. Это невозможно сделать лучше. DP обычно используется для максимизации или минимизации цели, которая должна быть достигнута. Для большинства встречающихся сумм я не нахожу какой-либо подзадачи, которую мы могли бы создать для этого.
Если эта задача связана с онлайн-соревнованиями судей/программистов, не могли бы вы предоставить ссылку на исходную формулировку задачи?
Ответы 1
Это разновидность проблема суммы подмножества. Это можно сделать за псевдополиномиальное время, где временная сложность равна О (n * сумма), используя динамическое программирование.
Рекуррентное отношение
dp(sum, i) = summation of dp(sum - a[i], i-1)
Объяснение
Представьте, что у вас есть решение для количества способов, которыми возможна любая сумма с подмножеством всех элементов от 0 до i-1. Обозначим его через dp(sum, i - 1) для всех значений sum. Чтобы включить новый элемент a[i] в действительное подмножество, составляющее sum, должно быть хотя бы одно решение для sum - a[i] в подмножестве элементов от 0 до i - 1. Тогда количество способов получить sum с подмножеством элементов от 0 до i становится суммой количества способов получить sum - a[i] с подмножеством элементов от 0 до i - 1.
Реализация
Реализация снизу вверх на C++ выглядит следующим образом:
int mostCommonSum(const vector<int>& a) {
int sum = 0;
for(auto num: a) {
sum += num;
}
vector<int> dp(sum + 1);
dp[0] = 1;
sum = 0;
for (int i = 0; i < (int)a.size(); i++) {
sum += a[i];
for(int j = sum; j >= 0; j--) {
if (j - a[i] >= 0) {
dp[j] += dp[j - a[i]];
}
}
}
int maxFrequency = -1;
int mostFrequentSum = -1;
for (int i = 0; i <= sum; i++) {
if (dp[i] >= maxFrequency) {
maxFrequency = dp[i];
mostFrequentSum = i;
}
}
return mostFrequentSum;
}
В реализации используется то же решение для динамического программирования. Однако это снижает сложность пространства, сохраняя решение только для dp(sum, i - 1) (а не dp (сумма, i - 2), dp (сумма, i - 3) и т. д.) как dp[sum].
Примечание. В ваших примерах чаще всего встречаются суммы 6, 8, 10, 12, 14. Обратите внимание, что при выборе только 1 элемента, т.е. 6, 8 тоже можно.
@HackNode Вы можете взглянуть на geeksforgeeks.org/subset-sum-problem-dp-25, чтобы получить общее представление о решении для динамического программирования. Я также добавил дополнительные пояснения. Надеюсь, это поможет.
Учитывая список
Nразличных целых чисел, у вас может быть2^Nразличных сумм. Он подозрительно похож на проблема суммы подмножества.