Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Подборка чисел в сумму


Автор: 1152010 10.11.2010, 02:42
Из базы выбираются записи, в одном из столбцов одни числа, средние между 10 и 100 обычно делимое на 5, но может и нет, кому как в голову стукнет.

Задача: Сказано собрать из этих чисел заданную сумму.

Никогда до этого с такой задачей не сталкивался, слабо представляю себе функцию.

 smile 

Автор: Akina 10.11.2010, 08:44
Классическая задача о рюкзаке в простейшем варианте - одномерная и без весовых коэффициентов.

Автор: 1152010 10.11.2010, 11:03
Akina, при всём уважение, ничего не понял.

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

Автор: Akina 10.11.2010, 12:36
http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%BD%D1%86%D0%B5

Автор: 1152010 10.11.2010, 14:47
Прочёл артикль, покликал по сылкам, взорвал себе мозг. Ранец не плох, но там два ограничения, мне хватит одного.
В добавок не совсем могу осмыслить как это всё смешать с запросами к MYSQL. так как выдовать все числа это - громадные затраты памяти и нагрузка на сервер.  smile 

Автор: Akina 10.11.2010, 15:22
ТАКИЕ задачи на SQL-сервере НЕ РЕШАЮТ!
SQL-сервер должен дать тебе сами числа. А вот реализация алгоритма подбора должна быть на клиенте. В твоём случае - на ПХП. Единственное удобство - ты можешь попросить от SQL-сервера дать тебе числа уже отсортированными, это немного упростит программирование алгоритма.

Автор: 1152010 10.11.2010, 15:44
Ну я не совсем сам SQL-иммел ввиду, вот так наваял пару дней назад, но чуствую что сильно не прав 
Код

if(!isset($_POST['sum']))
    {
    ?>
    <form action="test.php" method="post">
    <input type="text" name="sum">
    </form>
    <?
    }
else
    {
    $sum = $_POST['sum']; //nuzhnaja summa
    $ids = array(); //kuda zapisyvaem nuzhnye id 
    $idsindex = 0; //indeks dlja array
    $amounts = array(); //kuda zapisyvaem nuzhnye amount
    $amindex = 0; //indeks dlja array
    $col1 = true;

    while($col1)
        {
        $result = mysql_query("SELECT * FROM test WHERE amount<".($sum+1)." AND id NOT IN (".$ids.") AND status=1 ORDER BY amount DESC LIMIT 10");
        $sql++;
        $col2 = true;
        while($col2 AND $row = mysql_fetch_assoc($result))
            {
            if(($sum-$row['amount'])>=0)
                {
                $sql2++;
                $sum = $sum - $row['amount'];
                $ids[$idsindex] = $row['id'];
                $amounts[$amindex] = $row['amount'];
                $idsindex++;
                $amindex++;
                if($sum == 0)
                    {
                    $col2 = false;
                    $col1 = false;
                    }
                }
            else
                {
                $col2 = false;
                }
            }
        }

Как видно из кода, я просто разгружал SQL тем, что ограничивал выборку на 10 штук, ищя следующие по номиналу число

Автор: Akina 10.11.2010, 16:04
Слушай, ты зачем SQL-сервер ставишь в неудобную позу? Получи одним запросом все свои числа, свали их в массив - и развлекайся на ПХП уже без него.

Автор: 1152010 10.11.2010, 17:17
Сейчас там для теста только 10.000 записей, а будет гораздо больше.... Не слишком ли много данных для передачи и для прогона потом массива?

Автор: Akina 10.11.2010, 18:36
10тыс. чисел от 10 до 100? ну так передавай не по одному, а пару величина-количество...

Автор: 1152010 11.11.2010, 08:10
Akina, 
Код

GROUP BY
 ?

Ок, допустим сделаю, но проблема в том, что я не понимаю алгоритм перебора данных   smile  smile  smile 

Автор: Akina 11.11.2010, 08:41
Цитата(1152010 @  11.11.2010,  09:10 Найти цитируемый пост)
GROUP BY ?

Код

SELECT amount
     , count(amount) as cnt 
FROM test 
GROUP BY amount 
ORDER BY 1 DESC

Цитата(1152010 @  11.11.2010,  09:10 Найти цитируемый пост)
 я не понимаю алгоритм перебора данных

В таком случае используй метод ветвей и границ на сортированном по убыванию наборе.

Добавлено через 1 минуту и 43 секунды
Как я понимаю, у тебя задача - найти ЛЮБОЙ вариант, а не все возможные, верно?

Автор: 1152010 11.11.2010, 16:39
Akina, Не сочтите меня за лентея, но я не понимаю всех этих фраз, я сидел несколько часов пытаясь вникнуть в алгоритм с ранцем написанным на вике, в ваши посты. Вы пишите слишком много мне непонятных слов, я с этим всем не знаком. Я буду очень рад, если вы бы могли вами написаное, перевести в простой русский язык, указать на путь действий, в каком порядке, что перебирать.

Немного больше информации:
В таблице около 5 полей, но для данной задачи важны только 2: ИД записи, и сумма в строке, после подборки, мне нужно будет изменить статусы тех строк, которые вошли в сумму. Строки повторятся не могут. Я обратился за помощью потому, что те алгоритмы которые пытался написать я, они очень долго обрабатываются и с увелечением суммы и количества записей в базе и величины суммы просто вешаются.

Автор: Akina 11.11.2010, 16:41
Гм... Ну ладно, всё одно делать пока нехрен... ща напишу поподробнее, если какая-нить клуша не припрётся с какой-нить ерундой.

Добавлено через 11 минут и 46 секунд
Значит, так. Будем реализовывать метод ветвей и границ в самом его колхозном варианте.

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

Берём первый элемент. Задействуем его (ставим в соотв. элемент единичку), добавляем его к сумме, фиксируем его номер. И далее:
Если текущая сумма меньше требуемой - пытаемся задействовать следующий за текущим элемент (пометка, прибавление, фиксация).
Если текущая сумма равна требуемой - мы счастливы, задача решена, берём элементы с единичками и выполняем апдейт (у нас же в массиве и колонка ИДов имеется, не так ли?).
А вот если сумма больше - шагаем назад. Проходим все подрад идущие единички, обнуляем их и пересчитываем сумму, затем проходим все подряд идущие нолики, пытаясь добраться до первой единички. 
Если добрались - обнуляем её (и пересчёт суммы), и задействуем следующий после неё элемент (единичка и пересчёт).
А вот если добрались до начала списка и не нашли единички - значит, сумму набрать не получится. О чём и сообщаем.

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

Автор: Akina 11.11.2010, 17:11
Поправка (вернее дополнение).
На шаге "если сумма больше - шагаем назад. Проходим все подрад идущие единички, обнуляем их и пересчитываем сумму, затем проходим все подряд идущие нолики, пытаясь добраться до первой единички" ПЕРВЫЙ раз обнуляем только свежедобавленную единичку, не производя возврата назад.

UPD. Нет, требуется поправка... ща.

Автор: 1152010 11.11.2010, 17:56
Цитата(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
Цитата

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

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

Автор: Akina 11.11.2010, 18:36
Ну в общем вот. Код написан на 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
Цитата(baldina @  11.11.2010,  18:34 Найти цитируемый пост)
задача такова, что решается только перебором. другое дело, что проходя, скажем, от меньшего к большему, можно откинуть и не просматривать заведомо неподходящие варианты. 

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

Автор: baldina 11.11.2010, 18:39
Цитата

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
Цитата(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
косяк. я сначала должен был 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, решение найдено

Автор: Akina 11.11.2010, 21:42
Цитата(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, решение найдено

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)