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

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

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

  

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

Akina, при всём уважение, ничего не понял.

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

http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%BD%D1%86%D0%B5

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

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

Ну я не совсем сам SQL-иммел ввиду, вот так наваял пару дней назад, но чуствую что сильно не прав 

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

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

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

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

Akina,  ?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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




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

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

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




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

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

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

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

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

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

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

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

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

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

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