Тема: Алгоритм равномерного распределения чисел подскажите

Здравствуйте!

Не подскажете ли алгоритм решения следующей задачки (если таковой существует):
Имеется произвольный набор положительных чисел. Требуется разделить этот набор на две части так, чтобы суммы чисел каждой части были равны или минимально различались. Т.е., по возможности, нужно разделить набор на две равные части.

Заранее спасибо

Re: Алгоритм равномерного распределения чисел подскажите

Сортируем по убыванию. присваиваем 1 значение 1группе далее бежим по массиву и присваиваем значение 2 группе пока сумма значений не привысит 1группу, после этого наращиваем 1группу и так пока не доберемся до последнего элемента

Re: Алгоритм равномерного распределения чисел подскажите

Спасибо. Буду пробовать.

Re: Алгоритм равномерного распределения чисел подскажите

Думаю, что вариант,предложенный SmeL, не даст оптимальное решение поставленной задачи.
При небольшом количестве чисел в наборе можно использовать простой перебор всех вариантов:

Option Explicit

Private Function IncBin(ByRef V() As Byte) As Boolean
Dim i As Long, j As Long
For i = 0 To UBound(V)
    If V(i) = 0 Then
        V(i) = 1
        For j = 0 To i - 1
            V(j) = 0
        Next j
    IncBin = True
    Exit Function
    End If
    IncBin = False
Next i
End Function

Private Sub VSum(ByRef A() As Double, ByRef V() As Byte, ByRef FirstSum As Double, ByRef SecondSum As Double)
Dim i As Long
FirstSum = 0
SecondSum = 0
For i = 0 To UBound(A)
    If V(i) = 1 Then
        FirstSum = FirstSum + A(i)
    Else
        SecondSum = SecondSum + A(i)
    End If
Next i
End Sub

Private Sub Split(ByRef A() As Double, ByRef V() As Byte, ByRef B() As Double, ByRef C() As Double)
Dim i As Long
Dim nB As Long, nC As Long
ReDim B(0 To UBound(A))
ReDim C(0 To UBound(A))

For i = 0 To UBound(A)
    If V(i) = 1 Then
        B(nB) = A(i)
        nB = nB + 1
    Else
        C(nC) = A(i)
        nC = nC + 1
    End If
Next i
ReDim Preserve B(0 To nB - 1)
ReDim Preserve C(0 To nC - 1)
End Sub

Private Sub OptV(ByRef A() As Double, ByRef B() As Double, ByRef C() As Double)
Dim V() As Byte
Dim minV() As Byte

Dim FirstSum As Double, SecondSum As Double
Dim minS As Double, S As Double
Dim i As Long
ReDim V(0 To UBound(A)) As Byte
ReDim minV(0 To UBound(A)) As Byte
'minS = 1000
For i = 0 To UBound(A)
    minS = minS + Abs(A(i))
Next i
While IncBin(V)
    Call VSum(A, V, FirstSum, SecondSum)
    S = Abs(FirstSum - SecondSum)
    If S < minS Then
        minS = S
        minV = V
    End If
Wend
Call Split(A, minV, B, C)
End Sub

'Задача: разбить массив действительных чисел A на два массива B и С таких,
'что S = abs(Sum(B[i])-Sum(C[j])) -> min
'Решение простым перебором всех вариантов,ни какой оптимизации
'В случае, если есть несколько вариантов решения, для которых S = 0,
'то будет выведен только первый
Public Sub MainSub()
Dim B() As Double, bSum As Double
Dim C() As Double, cSum As Double
Dim i As Long
Dim t As Date

'Число элементов массива (При N>20 компьютер может на долго задуматься)
Const N = 19
'Создание массива
Randomize
Dim A(0 To N - 1) As Double
For i = 0 To N - 1
    A(i) = Rnd * 10
Next i
'Поиск решения
t = Time
Call OptV(A, B, C)
t = Time - t
'Вывод результатов
Debug.Print "First array:"
For i = 0 To UBound(B)
    bSum = bSum + B(i)
    Debug.Print B(i)
Next i
Debug.Print "Sum = " & bSum

Debug.Print ""
Debug.Print "Second array:"
For i = 0 To UBound(C)
    cSum = cSum + C(i)
    Debug.Print C(i)
Next i
Debug.Print "Sum = "; cSum
Debug.Print "Delta = " & Abs(bSum - cSum)
Debug.Print "Array size = " & N
Debug.Print "Time = " & t
'Время работы:
'PIV 1500 MHz
'Array size = 20
'Time = 0:00:08
'Увеличение N на 1 увеличивает время работы в 2 раза :(
End Sub

Код черновой,работает долго, но верно:)
Данный алгоритм можно(нужно) оптимизировать,например, отбросить рассмотрение заведомо ложных вариантов.

Re: Алгоритм равномерного распределения чисел подскажите

wl2000,

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


В общем если я правильно понял задачу, то в вашем случае можно сделать все просто, нужно просуммировать все значения из списка А (исходный список) и поделить поровну - т.е. найти арифметическую середину (sumA).

После чего, создать второй список (B), куда будут последовательно копироваться значения из первого списка. По мере копирования вы суммируете складируемые значения (sumB) и проверяете не преодолена ли значение SumA. Как только будет выполнено условие SumB>=SumA, копирование прекращается. Копируете остаток списка A в новый список (С). В результате у вас получаются два равных или примерно равных списка. В принципе, на этом задача не заканчивается. Дело в том, что создавая список B мы ориентировались на достижение и преодаление средины. Может оказаться тот случай, когда недобор 1 значения до середины будет ближе к середине нежели перебор (наш случай). Поэтому, это нужно проверить из списка 1 вычесть последнее значение и добавить к списке 2 - проверить разницу с SumA. Если разница будет меньше, то оставить так. Если больше, то вернуть как было.

Re: Алгоритм равномерного распределения чисел подскажите

> Гость
Сомневаюсь в верности Вашего решения, быть может Вы приведете код и развеете мои сомнения?

Re: Алгоритм равномерного распределения чисел подскажите

решение какой именно задачи? я решал задачу - деление списка на равные части по значению сумм при условии запрета сортировки значений. При условии запрета сортировки (по возрастанию значений или по убыванию) - алгоритм работает верно.

В случае допустимости сортировки, то можно применить более простой и быстрый алгоритм. шаг1. сортировка списка по возрастанию. шаг2. вычисление среднего значения (половина суммы всех значений). шаг3. определение середины методом половинного деления.

вот и все!

Re: Алгоритм равномерного распределения чисел подскажите

> Гость
И все-таки Вы не развеяли моих сомнений.
Условие задачи в посте №1

Пример: 2,3,10,4,1,5
В соответствии с предложенным Вами алгоритмом:
1.Сортируем по возрастанию
1,2,3,4,5,10
2.Половина суммы всех значений: (1+2+3+4+5+10)/2=12.5
3.Поиск решения
1+2 = 3 < 12.5
1+2+3 = 6 < 12.5
1+2+3+4 = 10 <12.5
1+2+3+4+5 = 15 > 12.5
Результат: (1,2,3,4,5) и (10)
Либо (1,2,3,4) и (5,10)
Разница сумм = 15-10 = 5

Решение (вернее одно из решений) полученное с помощью алгоритма, предложенного мною в посте  28.05.2009 10:04:47
(1,2,4,5) и (3,10)
Разница сумм = 1
Второе решение оптимальнее первого,т.к. 1<5
Поправьте меня, если я не прав. Лучше в виде кода.

(изменено: Гость, 28 мая 2009г. 15:17:58)

Re: Алгоритм равномерного распределения чисел подскажите

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

второй алгоритм: пожалуй, при отсортированном ряде половинное деление ничего не даст. :(

Re: Алгоритм равномерного распределения чисел подскажите

> Гость

второй алгоритм по сути является оптимизацией вашего

Не могу с Вами согласиться.
Во-первых, Ваш алгоритм не проверяет все возможные варианты
Во-вторых, результат работы у алгоритмов различный (пост 28.05.2009 14:13:15)

По поводу изменения порядка следования элементов в исходном наборе может ответить только автор вопроса.
Если порядок следования необходимо сохранить, то предложенный мною алгоритм конечно же будет не верен.

Re: Алгоритм равномерного распределения чисел подскажите

Mikha пишет:

Думаю, что вариант,предложенный SmeL, не даст оптимальное решение поставленной задачи.

Пример ряда в студию :)

Re: Алгоритм равномерного распределения чисел подскажите

> SmeL

Пример ряда в студию

Сначала Вы пишете код,реализующий предложенный Вами алгоритм, а затем я постараюсь найти ряд, доказывающий правомерность моих сомнений.
Подставляем мой тест в Ваш код и видим результат.
Но для начала нужно все-таки решить вопрос о возможности изменения первоначального порядка следования элементов в исходном наборе. Считаю, что изменять порядок можно и нужно, иначе задача становится слишком простой и недостойной нашего внимания:)

Re: Алгоритм равномерного распределения чисел подскажите

> SmeL
Извини, зря сомневался в правильности предложенного тобой способа решения задачи. Он не только верен, но и гораздо быстрее того, что предложил я. Если их сравнить, то получаем следующее:
1.Способ SmeL
+гораздо быстрее
-находит одно решение
-/+ не верен, если в наборе есть отрицательные числа (по условию задачи их быть не должно)
2.Способ Mikha
-работает очень медленно,при N>30 человек может и не дождаться результатов
+работает с отрицательными числами
+находит все возможные решения

Re: Алгоритм равномерного распределения чисел подскажите

Задание. Составить алгоритм построения ряда распределения дискретной случайной величины, нахождения функции распределения, математического ожидания, дисперсии, среднего квадратичного отклонения.                                        
                  Оформить программу в среде MS Excel на языке программирования Visual Basic for Application (VBA).                                       
        n=6        p=0,52