VPF::Подборка чисел в сумму - Форум программистов

1152010

Дата 11.11.2010, 17:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 38
Регистрация: 6.11.2010

Репутация: нет
Всего: нет

Цитата(Akina @ 11.11.2010, 16:41

)

Если текущая сумма меньше требуемой - пытаемся задействовать следующий за текущим элемент

А зачем? например сумма 480 первый самый большой на 450, а потом 50 варинтов пока не попадётся 20ка.

Но в принцепе я так и делал, перебирал всё по очереди, но вот только замечание от skyboy очень верно подметило слабую сторону перебора всех значений.

Цитата(skyboy @ 7.11.2010, 02:25

)

в смысле, в первую очередь выбирать максимально допустимое из имеющихся чисел?
тогда на наборе 5,4,3,2 собери 10(5 + 4 + ... а дальше что? с другой стороны, 5 + 3 + 2 дают как раз 10).

Или я не правельно понял вами написаное? smile

baldina

Дата 11.11.2010, 18:34 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 4
Всего: 101

Цитата

замечание от skyboy очень верно подметило слабую сторону перебора всех значений

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

Akina

Дата 11.11.2010, 18:36 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Ну в общем вот. Код написан на VBA. В MS Access 2003 на двухголовом пне 1.8 (всё равно используя только один проц) обрабатывает 10 тыщ записей за 8-10 секунд. Тыщу записей - за время менее дискретности системного таймера (55 мс).

Код


Private Const cnt As Integer = 10000 ' кол-во чисел
Private Const lim As Long = 32000 ' диапазон чисел от нуля и до
Private Const sum As Long = cnt * lim / 5 ' сумма, которую будем набирать

' Переменные
Dim x(0 To cnt, 0 To 1) As Integer ' массив значений и флагов включённости в сумму
Dim i As Integer
Dim j As Integer
Dim s As Long ' текущая сумма
Dim n As Integer ' текущий номер элемента

' процедура поиска (только констатирует факт, без вывода варианта)
Private Sub vg()

' Формируем массив и сортирим пузырём по убыванию
Randomize Timer
For i = 1 To cnt
    x(i, 1) = Rnd * lim 
Next
For i = 1 To cnt - 1
    For j = i + 1 To cnt
        If x(i, 1) < x(j, 1) Then
            x(i, 1) = x(i, 1) - x(j, 1)
            x(j, 1) = x(i, 1) + x(j, 1)
            x(i, 1) = x(j, 1) - x(i, 1)
        End If
    Next
Next

' фиксим время начала и понеслась
Debug.Print Time
n = 0
Do
    If n = cnt Then
        If GoBack Then
            Exit Do
        End If
    End If
    n = n + 1
    x(n, 0) = 1
    s = s + x(n, 1)
    If s = sum Then
        Debug.Print "Found."
        Exit Do
    End If
    If s > sum Then
        If n < cnt Then
            x(n, 0) = 0
            s = s - x(n, 1)
        Else
            If GoBack Then
                Exit Do
            End If
        End If
    End If
Loop
' фиксим время окончания
Debug.Print Time

End Sub

' функция возврата
Private Function GoBack() As Boolean
GoBack = False
While x(n, 0) = 1
    x(n, 0) = 0
    s = s - x(n, 1)
    n = n - 1
    If n = 0 Then
        Debug.Print "NOT Found."
        GoBack = True
        Exit Function
    End If
Wend
While x(n, 0) = 0
    n = n - 1
    If n = 0 Then
        Debug.Print "NOT Found."
        GoBack = True
        Exit Function
    End If
Wend
x(n, 0) = 0
s = s - x(n, 1)
End Function

Цитата(1152010 @ 11.11.2010, 18:56

)

например сумма 480 первый самый большой на 450, а потом 50 варинтов пока не попадётся 20ка

нет проблем - оптимизируй, введи пропуск заведомо больших значений.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

1152010

Дата 11.11.2010, 18:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 38
Регистрация: 6.11.2010

Репутация: нет
Всего: нет

Цитата(baldina @ 11.11.2010, 18:34

)

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

Это как? можно поподробней?

baldina

Дата 11.11.2010, 18:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 4
Всего: 101

Цитата

5,4,3,2 собери 10

5 < 10
5+4 < 10
5+4+3 > 10, возврат
5+3 < 10
5+3+2=10, решение найдено

2,3,4,5 собери 10
2 < 10
2+3 < 10
2+3+4 < 10
2+3+4+5 > 10, возврат
2+3+5=10, решение найдено

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

Добавлено через 1 минуту и 13 секунд
а как именно это реализуется - см. пример Akina

1152010

Дата 11.11.2010, 18:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 38
Регистрация: 6.11.2010

Репутация: нет
Всего: нет

Цитата(baldina @ 11.11.2010, 18:39

)

5 < 10
5+4 < 10
5+4+3 > 10, возврат
5+3 < 10
5+3+2=10, решение найдено

А по какому программно логическому ходу, ты отменил 4 а не 3? Вот иммено этот момент мне интересен, как избавится от слишком громадного перебора ненузжного? Может существуют вообще функции какие-то математические, с помощью которых это можно упростить?

baldina

Дата 11.11.2010, 18:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 4
Всего: 101

косяк. я сначала должен был 2 попробовать)))

Добавлено @ 18:53

Цитата

как избавится от слишком громадного перебора ненузжного

этому и служит метод ветвей и границ

Добавлено @ 18:55
его мы и применяем. а уж как производить оценки, зависит от задачи
а просто перебор означал бы последовательную генерацию всех подмножеств и остановку, когда сумма станет 10

Добавлено @ 18:57

Цитата

5 < 10
5+4 < 10
5+4+3 > 10, возврат
5+3 < 10
5+3+2=10, решение найдено

5 < 10
5+4 < 10
5+4+3 > 10, возврат
5+4+2 > 10, возврат
5+3 < 10
5+3+2=10, решение найдено

Это сообщение отредактировал(а) baldina - 11.11.2010, 18:58

Akina

Дата 11.11.2010, 21:42 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(baldina @ 11.11.2010, 19:51

)

5 < 10
5+4 < 10
5+4+3 > 10, возврат
5+4+2 > 10, возврат
5+3 < 10
5+3+2=10, решение найдено

Приведённый мной код именно так и работает.

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »