Решение проблемы подмножества сумм с большими суммами и десятичными разрядами - PullRequest
Новая
       1

Решение проблемы подмножества сумм с большими суммами и десятичными разрядами

0 голосов
/ 08 июля 2011

Ищем решение проблемы суммы подмножеств для этого конкретного случая (в C # или другом алгоритме):

1) В наборе около 1000 чисел (может возрасти до нескольких тысяч)

2) Суммы исчисляются в миллиардах

3) Числа являются валютными значениями, поэтому имеют точность до двух десятичных знаков (например, 2345,17)

4) Числа в наборе могут быть как положительными, так иотрицательный (то есть с чистой суммой)

Затем мне нужно повторить этот поиск (с тем же набором чисел), но с другой суммой, до 1000 раз.И, наконец, весь процесс выполняется 1000 раз.Итак, мы смотрим на 1 000 000 пробежек.Цель состоит в том, чтобы выполнить это за 2 минуты.Это означает, что каждый прогон должен занимать не более 0,12 мс.

Это возможно?

-Krip

1 Ответ

0 голосов
/ 08 июля 2011

Я предполагаю, что вы уже знаете о псевдополийном алгоритме DP, который является практически единственным дистанционно (для оптимальных ответов) способ сделать это для 1000 элементов

Способ, которым обычно реализуется алгоритм, включает в себя массив размера максимальной суммы, каждый из которых представляет отдельный сегмент для числа с этим индексом. Чтобы адаптировать это к десятичным числам, вам нужно преобразовать ваши данные из десятичного в целое (умножив на 100). Вы также можете реализовать это, используя заданную структуру данных, которая может быть намного проще и эффективнее.

например., 

import copy
j = {0:1}
lst = [1,2,8,2.3,214]

for i in lst:
    newj = copy.copy(j)
    for k in j:
        newj[k+i]=1
    j = newj

Повторение алгоритма суммы поднабора с другой суммой не должно быть проблемой - если вы будете следовать алгоритму DP, вы вычислите все возможные суммы один раз, а затем сможете каждый раз перепроверять свой набор для новой суммы ,

Реальная проблема заключается в размере вашего набора, так как он будет расти по мере продвижения алгоритма. В худшем патологическом случае размер набора будет расти экспоненциально с количеством элементов (каждая сумма уникальна, 2 ^ n элементов). Если есть некоторые совпадения, вам будет лучше. Я предполагаю для 1000 элементов, хотя, с большим диапазоном, у вас могут быть проблемы.

...