Доброго времени суток) Обратился знакомый с вроде простой задачей - есть экселька на ~1000 строк с разными суммами, надо выбрать наиболее подходящие суммы к некоторой константной, которую вводит пользователь. Нашел пример решения полным перебором (от гения 1С) - но до этого я и сам практически дошел. А вот как это еще можно решать? К сожалению, математику совсем позабыл.. То, что в ютубе говорят в мозг не ложится. Может кто-то либо простым языком объяснить, либо дать пример решения?

+ Полный перебор не катит - т.к. долго.. ФИФО не катит - т.к. неоптимально..

а где мой коммент? или опять глючит

Да вот тоже не увидел. Напиши еще раз?

> А вот как это еще можно решать?

1. Отсекай ветви.
2. Поставь удовлетворяющую точность.
3. Поставь ограничение по времени и по окончании бери самый удовлетворительный.

см. метод ветвей и границ

(4) Дай хотя бы самый общий анализ.

Если тебе надо набрать константу 100

А цифры из списка имеют значение в среднем 25-35, то это одно, а если цифры имеют значение 2-3 это другое.

(0) Можно расшифровать:
"наиболее подходящие суммы к некоторой константной"

Сумма чисел должна равнятся некой константе?

(7) Задает например пользователь 2 миллиона. А числа - 35 тыс, 80 тыс, 219 тыс, 1,5 тыс и т.д. Вот среди них надо выбрать такие, которые в совокупности дают наибольшее / наилучшее приближение к этому числу.
Т.е. если по фифо - сортируем по возрастанию, и подбираем среди наименьших до тех пор пока их сумма не станет наиболее близка к критерию. Но в результате всегда будет остаток. Например если пользователь вбивает 11, а числа - 1,2,3,4,5,6... То ФИФО выберет 1+2+3+4. А надо 2+4+5.

(6) Спасибо за совет, попробую покопать.. Вчера смотрел пару лекций - что-то вообще в голову не легло..

(0) Задача распараллеливается?

(11) не понял?

А, нет.. Да как-то и не понимаю как ее можно распрараллелить.. Там же один рекурсивный цикл

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

(0) Запросом?

(13) Чего там понимать то, последующие рекурсивные циклы запускаешь со 2, 3 и т.д. элементов.
Причем во всех циклах предусмотрено пропускать уже заюзанные начальные элементы.

Для 2 процессов:
1-й процесс цикл с 1-го элемента, пропускает 2-й, 4-й и 6-й и т.д.
2-й процесс цикл идет со 2-го элемента, пропускает 3-й, 5-й и т.д.

Причем пропуск (по условию) только на самом верхнем уровне, далее все элементы смотрит для выборки-укладки.

(16)+ Если хочешь решения задачки "очень быстро-быстро" то гугли OpenCL и CUDA.

Если готовы платить то могу наваять, видеокарту за 5 т.р. то надеюсь найдете ))

(17) да ну, мне ж в 1С надо) ВК не умею) Скинул ветку знакомому, вернее знакомой, она может быть свяжется с вами, спасибо за предложение. Сам уже загружен другим, может позже как время будет поковыряюсь чисто для себя.
- Посмотреть "метод ветвей и границ"
- Подумать над возможностью вычислять рекурсию в параллельных потоках

(9)> Т.е. если по фифо - сортируем по возрастанию, и подбираем среди наименьших до тех пор пока их сумма не станет наиболее близка к критерию.

Глупость вот тебе надо 2 миллиона.

есть две цифры 500 000 и 1 500 000.

И есть циры 3.45, 7.89, 9.33

Тут неизвестно с каких цифр лучше начать искать.

И еще вопрос: а можно ли одну и ту же цифру два раза использовать?

(10) Обратись к классикам: http://algolist.manual.ru/maths/combinat/sequential.php

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

(19) ФИФО по твоему примеру возьмет 3.45 + 7.89 +  9.33 + 500 000. А жадный рюкзак как раз 500 000 и 1 500 000.
Сколько строк, столько и сумм. Если есть две строки по 10000 то можно два раза использовать 1000.
(21) Так нет четких критериев. Единственный критерий - итог подобранных сумм должен быть наиболее оптимален. Т.е. подобрать из наименьших так, чтобы приближение стремилось к 100% совпадения с исходной суммой.

*Если есть две строки по 10000 то можно два раза использовать 1000. - опечатался. Если есть две строки по 10000 то можно два раза использовать 10000.

Кстати, мб тут задачка по пределам?.. Функция от X стремится к числу..

lim F(x)
x->СуммаКритерия

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

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

&НаСервере
Функция ИндексыСуммПриближения(ТаблицаСумм, СуммаКритерий)
    
    ТаблицаПриближений = Новый ТаблицаЗначений;
    ТаблицаПриближений.Колонки.Добавить("Сумма", Новый ОписаниеТипов("Число"));
    ТаблицаПриближений.Колонки.Добавить("Отклонение", Новый ОписаниеТипов("Число"));
    ТаблицаПриближений.Колонки.Добавить("Индексы");
        
    ВГраницаСтрок = ТаблицаСумм.Количество()-1;
    
    Для СчетчикСтарта = 0 По ВГраницаСтрок Цикл
        
        СуммаКПогашению = СуммаКритерий;
        
        Приближение = ТаблицаПриближений.Добавить();
        Приближение.Индексы = ОбщегоНазначенияКлиентСервер.ЗначениеВМассиве(СчетчикСтарта);
        
        СтрокаСтарта = ТаблицаСумм[СчетчикСтарта];
        Для СчетчикПрохода=0 По ВГраницаСтрок Цикл
            
            Если СчетчикПрохода < СчетчикСтарта Тогда
                Продолжить;
                
            ИначеЕсли СчетчикПрохода = СчетчикСтарта Тогда
                ТекСумма = СтрокаСтарта.Сумма;
                
            Иначе
                СтрокаПрохода = ТаблицаСумм[СчетчикПрохода];
                ТекСумма = СтрокаПрохода.Сумма;
                
            КонецЕсли;
            
            Рез = МАКС(СуммаКПогашению, СуммаКПогашению - ТекСумма);            
            СуммаКПогашению = СуммаКПогашению - ТекСумма;            
            Если СуммаКПогашению <=0 Тогда
                Прервать;                
            КонецЕсли;     
            
            Приближение.Индексы.Добавить(СчетчикПрохода);            
            Приближение.Сумма = Приближение.Сумма + ТекСумма;
        КонецЦикла;
        
        Приближение.Отклонение = СуммаКритерий - Приближение.Сумма;        
    КонецЦикла;
    
    ТаблицаПриближений.Сортировать("Отклонение");
    СтрокаРезультат = ТаблицаПриближений[0];
    Сообщить("Отклонение по наименьшим = " + СуммаКритерий + " - " + СтрокаРезультат.Сумма + " = " + СтрокаРезультат.Отклонение);
    
    Возврат ТаблицаПриближений[0].Индексы;
    
КонецФункции

(22)
> Так нет четких критериев. Единственный критерий - итог подобранных сумм должен быть наиболее оптимален. Т.е. подобрать из наименьших так, чтобы приближение стремилось к 100% совпадения с исходной суммой.

Как раз, наибольшее приближение к требуемой сумме, и при первом найденном равном остановить поиск - это четкий критерий. Тут нет понимания, сколько чисел может влезть в требуемую сумму. Там комбинаторный вопрос, объем вычислений которых возрастает факториально. Если до десяти штук - то обсчитать все пространство вариантов, если больше, то все зависит от ситуации. А дальше рекурсивный алгоритм перебора по сортированному списку чисел. Делал когда то, стоит дорого.