Имеется: таблица значений с n столбцов и i строк. Значения числовые.
Необходимо: из имеющегося набора выбрать строки так, чтобы итоговая сумма по столбцу по отобранным строкам равнялась некоторому заданному целевому значению. Целевые значения для столбцов различаются. Также допускается погрешность итоговой суммы относительно целевого значения. Допустимая погрешность для разных столбцов тоже различна.
В сторону каких алгоритмов копать?

в сторону рюкзака

(0) Эээ... И что? В чем сложность сравнить n значений с целевым значением?

(2) в том что строчек много?

(1) Угу, по сути задача о рюкзаке. Многомерном. Подозреваю, что генетические придется освоить.

можно и примитивным перебором

Тебе же для всех столбцов нужно сразу найти эти строки, чтоб суммы хоть примерно соответствовали?

Если табличка маленькая, то можно и перебором перебрать все решения и выбрать оптимальное - тут вообще никакого алгоритма не надо будет. Правда, быстродействие не алё, но на малой табличке и так сойдёт :)

(7) +как вариант:
В цикле пока (ВремяКотороеМыОтвелинаРаботуАлгоритмаНеВышло)
кидаем рандомные строчки, запоминаем лучшую по критериям достижимости

(7) 500000 строк, 9 столбцов

(7) (9)  Ну да 2^500000 вариантов - не дождетесь

(0) Нужно отобрать(подобрать) строки чтобы итоги по всем столбцам были равны требуемым?
По одному столбцу не катит, так?

(7) Только для языка 1С "маленькая табличка" - это всего 9 записей. Я делал. 10 записей - не дождался полного перебора.

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

(13) Ну а чего - рюкзак решить по количеству столбцов отдельно, найти пересечения в решениях.

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

еще можно по оптимизации подумать

вообщем по шагам:
1. Подбираем все наборы строк для каждого столбца
1.1. Отсортировать по нужному стобцу
1.2. Умный подбор всех вариантов наборов строк смотря какая нужна сумма
2. Ищем пересечения наборов последовательно, т.е. множества наборов строк 1-го столбца пересекаем с множеством наборов строк 2-го столбца
3. И т.д. продолжаем пересекать найденные в п.2 набор для 3-го столбца (1+2 нашли, дальше ищем (1+2)+3)

(15) Учитывая (9), все советы вообще не в кассу

(15) Нереально, уже начиная с 1

+(17) за приемлемое время, естественно

(17) (18) приемлемое время это сколько? с учетом (9)

(17) Всё реально. 50 МБ на один столбец, если, конечно, решение вынести куда-нибудь в С++

(19) + к примеру понятие "итог по столбцу" это как минимум 2 строки так?

можно сразу отсечь варианты по превышению суммы с 3-мя и более строками
таблицу умножения помним?
представляем подобную таблицу сложения из значений столбца
если сумма больше искомой то выкидываем эти строки они уже того

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

(20) Как уже замечено в (10) при общем наборе строк в 500000 количество возможных вариантов наборов строк = 2^500000.
О каких 50МБ идет речь мне немного непонятно.

(22) а зачем нужно каждую строчку с каждой соединять для проверки?
наверняка же ограничение по итоговой сумме
нету ведь такого варианта что 100 000 строк нужно сложить для какого то столбца?

>> (23) нету ведь такого варианта что 100 000 строк нужно сложить для какого то столбца?
Это заранее неизвестно.

(24) у Вас извините практика или теория?

(25) У нас реальная задача)

(26) может тогда реально ее опишите?
а не теоретически

Да если значения в таблице очень малы по сравнению с требуемыми итогами по столбца
И при наличии нужной вероятности распределения значениц в таблице

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

(28) для примера ))

пусть нужно подобрать 1-2-3
есть
1-0-0
0-1-0
0-0-1
1-1-1

решение
1-1-1
0-1-0
0-0-1
0-0-1

принцип понятен?

Все уже сделано до вас (неоптимально, некрасиво, но пиплов и не одного удовлетворило)

Мой гений дарит вам (в Белоруссии все гении - и Г1С и я)

http://catalog.mista.ru/public/14526/

[Z-report] "Битва титанов v.1" Подбор продаж под сумму Z-отчета
Обработка служит для мелкой автоматизации бардака. Например: приносят бухгалтеру Z-отчет на сумму сто тыщ мильенов рублей, а бухгалтер сиди и думай - чего бы продать такого, чтоб набрать требуемую сумму, при этом еще наценку показать в размере 23-25% (то есть еще и себестоимость...)... вот эту рутинную работу и берет на себя данный шедевр автоматизации.

(30) проблема что ТС требуется оно самое почти
но для 9 разных сумм одновременно подогнать из имеющихся

т.е. упрощенно пусть есть цена закупки З и цена продажи П
и хочется манипулирую видами товаров и их кол-вом подогнать под нужные СуммаЗ(акупки) и СуммаП(родажи) ;)

1. Если число подходящих вариантов для одного столбца "невелико" (меньше 5-6), можно попробовать поискать пересечения множеств по столбцам (например, схемой ветвей и границ).
2. Можно попробовать применить схему ветвей и границ к исходной целочисленной задаче, используя в качестве отсечения "неперспективных" ветвей решение задачи линейного программирования (поиск допустимого решения).
На всякий случай, задача выглядит так: нужно найти решение системы целочисленных неравенств:
B1j<=СУММА(Aij*Xi)<=B2j
Xi = 0 или 1.
Редукция к задаче ЛП: 0<=Xi<=1.
Боюсь, правда, что для 500 000 переменных решение задачи ЛП заткнется и дело не в 1С (для задачи ЛП эмпирическая оценка числа итераций симплекс-метода - 3*M*N. В Вашем случае M = 9+500 000, N = 500 000. При этом каждая итерация требует порядка N^3 операций).
Более того, просто решение системы линейных уравнений с таким числом переменных затруднительно (если только матрица не имеет специальной структуры - 3-х, 5-ти диагональная - тогда подходят методы прогонки.
Наверное, нужно переформулировать задачу.
(30) Присоединяюсь к (31): одномерный ранец можно практически решать быстро с приемлимой точностью (жадным алгоритмом).

Как такая простенькая идейка?
Допустим надо подобрать 9 20 8
Общая сумма по столбцам 37
Рассчитываем коэффициент для каждого столбца
0,24 0,54 0,21

Для каждой строки вычислим также вычисляем коэффициенты, причем вычислить можно заранее и записать в регистры

Для подбора сортируем строки по минимальной разнице от требуемых коэффициентов
Для строки с коэффицентами 0,20 0,50 0,20  разница будет меньше чем строка с коэффицентами 0,50 0,20 0,30

Дальше примитивный перебор.

Математически не совсем решение, но для 1С, думаю, подойдет.

(33) и чем оно отличается от (29) ? :)

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

не лучше ли все строчки разделить на группы (по этим коэффициентам)

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

из них и собираем (набираем) что нужно

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

(33) Т.е. выбирать строки, наименее уклоняющиеся от пропорций по по столбцам (метрику можно и минимальное отклонение и квадратичное - без разницы)?
В многомерном ранце это означает на каждом шаге выбор строки, наименее уклоняющейся от вектора из достугнутого состояния в (B1, B2, ..., Bk).
Скорее всего, эта идея в многомерном ранце прокачивалась.
Я бы попробовал.

(35) Вот бы мне научиться так выражать свои мысли. Где такому учат? :)

(0) Обозначьте порядок чисел в таблице и порядок сумм в столбцах (и отклонений для них): если будет время, сделаю обработку для тестирования и сбора статистики по (33).

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

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

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

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

Кстати, для задачи ЛП есть примеры задач, когда число итераций симплекса экспоненциально по числу переменных, а на практике - О(N*M).
Да и для систем линейных уравнений есть примеры неустойчивых задач.
(38) Отсечения сделать нелишне, только вряд ли это сильно понизит размерность.

В общем, попробовал аналог (33) (время линейно по числу строк).
Матрица - случайная с характерным размером - 100.
Правые части - случайные от 30% до 70% от суммы по строкам в столбце.
Для 5000 строк и 6 столбцов 3-4 сек
Для 20 000 - 14 сек.
Наверное можно ускорить.
НО! Ни разу не удалось попасть в 2% коридор от значений правых частей. Для 20 000 строк лучший результат (20 задач) по отклонению (расстояние между решением и вектором правых частей/модуль вектора правых частей)- 0,14. Для 5000 - 0,05.
Если будет желание - сделаю (35).

Экспромтом.

Набросок алгоритма /но не алгоритм/.

Для начала строишь binary tree из исходного набора чисел /по отношению к требуемой сумме ReqSumma/.
При этом для каждой ветви /node/ устанавливаешь его вес /пусть node справа > 50% от суммы/.
Скорее всего вес ветки node должен рассчитываться по формуле ReqSumma / 2 ** level.
Обозначим вес node справа RViegt, слева LViegt, текущий вес перебора RViegt
Что это даст?
Сокращение числа переборок.
Берешь скажем скажем первый справа node и далее производишь перебор тех веток слева у которых
RViegt + ВесNode <= 100 /для упрощения алгоритма можно использовать рекурсию/.

(0)Что такое целевое значение?

(41)+.
Вчера "наврал" (была ошибка): точность в реализации (33) несколько лучше: около 10% (но есть и попадания в 2% коридор).
Реализация по (35) (пересчет коэфф. близости по направлению после каждого выбора строки) по точности лучше (в несколько раз, но не на порядок): чаще попадает в коридор. Но его трудоемкость квадратичная по числу строк: для 1000 расчет длится 50сек (в 1С), поэтому 500 000 точно не потянуть. До 10 000 еще можно попробовать.
(0) Если еще есть интерес, пишите на мыло (в профиле) - вышлю обработку.