#algorithm
#алгоритм
Вопрос:
0K, вот в чем проблема, я постараюсь сделать это как можно более понятным.
Итак, у нас есть массив пар ключ-значение в виде уникальный идентификатор => число.
массив псевдокода A= array(0 => 17, 1 => 26, 2 => 17, 3 => 2, 4 => 7, 5 => 8);
мы видим, что общее количество чисел равно 60. ЭТО ВСЕГДА ПРАВИЛЬНО, ПОЭТОМУ СУММА В МАССИВЕ A ВСЕГДА ПРАВИЛЬНАЯ.
теперь у нас есть массив B в массиве B, также уникальные пары id => value, НО здесь некоторые значения ПОДДЕЛЬНЫЕ / НЕПРАВИЛЬНЫЕ, и total (массив B)-total(массив A) должно быть 0.
т.е. для верхнего примера массива A= array(6 => 22, 7 => 11, 8 => 8, 9 => 9, 10 => 5, 11 => 10, 12 => 7, 13 => 17, 14 => 10);
теперь общее количество массивов B равно 99. 60-99 = -39, что означает, что мы должны найти все комбинации чисел, равные 39, из массива B. в этом случае, просто глядя на глаз, кажется, что возможны только две комбинации этого: что уникальные идентификаторы 10, 12, 13, 14 неверны или что 10, 11, 12, 13 являются ФАЛЬШИВЫМИ / НЕКОРРЕКТНЫМИ (5 7 17 10=39). теперь, с такими маленькими массивами, их легко найти, используя циклы и перебирая все возможные варианты, но с массивами, насчитывающими тысячи (уникальных идентификаторов). каков наилучший способ сделать это? как бы компьютер быстрее всего находил фальшивые / неправильные пары?
Кроме того, я должен пиво человеку, который дает лучший (и хороший) ответ.
Комментарии:
1. Хм, человек, стоящий за анонимным аккаунтом, предлагает мне бесплатное пиво. Заманчиво, но … не-а.
2. чем больше массив, тем больше будет расти число «допустимых» комбинаций. Если быть уверенным, перед проверкой я бы отсортировал «b» по значению и исключил все значения, превышающие разницу.
3. Это проблема суммы подмножеств
Ответ №1:
теперь общее количество массивов B равно 99. 60-99 =-39, что означает, что мы должны найти все комбинации чисел, равные 39, из массива B.
Это верно только в том случае, если вы знаете, что все неправильные числа должны были быть нулями.
Любое или все числа в массиве могут вносить вклад в ошибку, отклоняясь на такие величины, что общая сумма ошибок равна 39.
При этом проблема нахождения подмножества списка чисел, которые складываются в определенную сумму, связана с задачей о сумме подмножеств, хотя обычная постановка задачи заключается только в проверке существования такого подмножества, и вы ищете список всех таких подмножеств.
Я не верю, что для больших наборов существует эффективное решение, и решение методом перебора растет экспоненциально.
Комментарии:
1. Как правило, количество таких подмножеств растет экспоненциально, поэтому повышается эффективность.
2. Это верно только в том случае, если вы знаете, что все неправильные числа должны были быть нулями. <- на самом деле это так. в данном случае числа не являются частично правильными, они либо полностью неверны, либо правильны. есть какие-нибудь идеи, как это сделать (конечно, грубая сила не вариант)?
3. Экспоненциальная временная сложность на самом деле может быть не такой уж сложной в этом случае. Псевдополиномиальное решение равно O (KN), где K — разность (например, 39). Итак, если вы знаете, что разница будет достаточно небольшой, это решение может быть довольно быстрым. И вы не найдете ни одного решения, которое было бы быстрее.