Это частный случай "задачи о рюкзаке", т.к. необходимо найти не оптимальный перечень слагаемых, а любую возможную комбинацию, удовлетворяющую заданным условиям. Думаю, что задача может иметь практическое применение.
У меня были некоторые наработки на эту тему, решил их доработать и опубликовать, а также хочется получить дополнительные материалы по эффективным алгоритмам. Считаю, что данную задачу нужно решать с помошью макросов (все решения через поиск решения или формульные варианты не рассматриваю).
На текущий момент, самый быстрый способ решения, который мне попадался - это "макрос Слэна", но у него есть недостаток, решение не всегда может быть найдено. Как именно работает макрос я не разобрался, но думаю, что в основе лежит "жадный алгоритм" с перебором.
Если есть ссылки на хорошие алгоритмы или реализации, прошу поделиться
Прилагаю файл с разными решениями: 1. Случайная выборка, не самый лучший вариант, но может и он сгодиться 2. С применением динамического программирования. Сумма находится по целочисленным слагаемым, работает относительно быстро и если может быть решение - оно будет найдено. Скорость, а также объем выделяемой памяти сильно зависят от искомой суммы, в макросе введено ограничение - сумма не должна превышать 80 000 000. Подходит для решения дробных сумм, например, рубли с копейками, достаточно все суммы умножить на 100. 3. Преребор (brute force), возможно указать ограничения по количеству слагаемых, а также отсекает неоптимальные ветви решения, что позволило сделать приемлемый по скорости перебор, находит все решения подходящие под условия. Но для большого количества слагаемых метод не применим 4. Макрос Слэна, хороший быстрый алгоритм, но не всегда находит решение.
Реализация не окончательная, поэтому в готовые решеня не размещаю. Хочется найти еще эффективные и быстрые варианты решения. Например, можно совместить частичный перебор с динамикой
UPD 27.02.2014: Обновлен алгоритм с перебором, стал существенно быстрее работать
Это частный случай "задачи о рюкзаке", т.к. необходимо найти не оптимальный перечень слагаемых, а любую возможную комбинацию, удовлетворяющую заданным условиям. Думаю, что задача может иметь практическое применение.
У меня были некоторые наработки на эту тему, решил их доработать и опубликовать, а также хочется получить дополнительные материалы по эффективным алгоритмам. Считаю, что данную задачу нужно решать с помошью макросов (все решения через поиск решения или формульные варианты не рассматриваю).
На текущий момент, самый быстрый способ решения, который мне попадался - это "макрос Слэна", но у него есть недостаток, решение не всегда может быть найдено. Как именно работает макрос я не разобрался, но думаю, что в основе лежит "жадный алгоритм" с перебором.
Если есть ссылки на хорошие алгоритмы или реализации, прошу поделиться
Прилагаю файл с разными решениями: 1. Случайная выборка, не самый лучший вариант, но может и он сгодиться 2. С применением динамического программирования. Сумма находится по целочисленным слагаемым, работает относительно быстро и если может быть решение - оно будет найдено. Скорость, а также объем выделяемой памяти сильно зависят от искомой суммы, в макросе введено ограничение - сумма не должна превышать 80 000 000. Подходит для решения дробных сумм, например, рубли с копейками, достаточно все суммы умножить на 100. 3. Преребор (brute force), возможно указать ограничения по количеству слагаемых, а также отсекает неоптимальные ветви решения, что позволило сделать приемлемый по скорости перебор, находит все решения подходящие под условия. Но для большого количества слагаемых метод не применим 4. Макрос Слэна, хороший быстрый алгоритм, но не всегда находит решение.
Реализация не окончательная, поэтому в готовые решеня не размещаю. Хочется найти еще эффективные и быстрые варианты решения. Например, можно совместить частичный перебор с динамикой
UPD 27.02.2014: Обновлен алгоритм с перебором, стал существенно быстрее работатьMCH
С точки зрения математики, Вашу задачу надо привести к системе линейных уровнений, которая в свою очередь решается уже разными методами, самым простым например - Simplex методом.
С точки зрения математики, Вашу задачу надо привести к системе линейных уровнений, которая в свою очередь решается уже разными методами, самым простым например - Simplex методом.PowerBoy
по теме есть куча теории: http://ru.wikipedia.org/wiki/Задача_о_сумме_подмножеств я нарисовал в экселе свой вариант решения, он ограничен семью слагаемыми, но зато довольно быстро работает для исходного множества в 100 слагаемых (из которых выбираем 7). Но вот уже на двухстах может "застрять" на час... Вообще, поскольку главная проблема с этой задачей - резкий рост времени расчёта, то в правильный вариант решения, на мой взгляд, необходимо включать оценку времени, которое понадобится. С гордостью могу заявить, что я несколько дней тестировал свой алгоритм, и сейчас он делает такую оценку сверху (времени, которое может понадобиться на подбор). Также есть возможность подбирать с указанной точностью (задаётся в ячейке "tolerance") и, если с указанной точностью сумма не возможна из данного списка, будет выведена ближайшая из возможных сумм.
по теме есть куча теории: http://ru.wikipedia.org/wiki/Задача_о_сумме_подмножеств я нарисовал в экселе свой вариант решения, он ограничен семью слагаемыми, но зато довольно быстро работает для исходного множества в 100 слагаемых (из которых выбираем 7). Но вот уже на двухстах может "застрять" на час... Вообще, поскольку главная проблема с этой задачей - резкий рост времени расчёта, то в правильный вариант решения, на мой взгляд, необходимо включать оценку времени, которое понадобится. С гордостью могу заявить, что я несколько дней тестировал свой алгоритм, и сейчас он делает такую оценку сверху (времени, которое может понадобиться на подбор). Также есть возможность подбирать с указанной точностью (задаётся в ячейке "tolerance") и, если с указанной точностью сумма не возможна из данного списка, будет выведена ближайшая из возможных сумм.watsonww
Спасибо MCH, что сообщил об ошибке, выкладываю исправленную версию.
Вообще, если задача сводится к целочисленным входным данным, то однозначно надо пользоваться алгоритмом динамического программирования, ну, если к тому же сумма меньше 80 млн. А вот если не сводится, вопрос остаётся открытым. Надеюсь, и мой вариант кому-нибудь может пригодиться.
Спасибо MCH, что сообщил об ошибке, выкладываю исправленную версию.
Вообще, если задача сводится к целочисленным входным данным, то однозначно надо пользоваться алгоритмом динамического программирования, ну, если к тому же сумма меньше 80 млн. А вот если не сводится, вопрос остаётся открытым. Надеюсь, и мой вариант кому-нибудь может пригодиться.watsonww
Доработал свой макрос с ограниченным перебором. Сделал дополнительную проверку по отсечению не оптимальных ветвей решения, скорость увеличилась на порядок
Доработал свой макрос с ограниченным перебором. Сделал дополнительную проверку по отсечению не оптимальных ветвей решения, скорость увеличилась на порядокMCH
Коллеги, привет! Нужна помощь - не могу подобрать сумму 0 (либо если нельзя - 103007,81) из выборки не целых положительных и отрицательных чисел (столбец A). Что делаю не так ? Может использовать другой способ ?
Заранее спасибо за ответы :victory:
Вопрос снят
Коллеги, привет! Нужна помощь - не могу подобрать сумму 0 (либо если нельзя - 103007,81) из выборки не целых положительных и отрицательных чисел (столбец A). Что делаю не так ? Может использовать другой способ ?
Добрый день. Подскажите пожалуйста, можно-ли осуществить подбор слагаемых, если они находятся в двух или трёх столбцах? И что в этом случае нужно исправить в коде макроса?
Добрый день. Подскажите пожалуйста, можно-ли осуществить подбор слагаемых, если они находятся в двух или трёх столбцах? И что в этом случае нужно исправить в коде макроса?Олег
Доработал свой макрос с ограниченным перебором. Сделал дополнительную проверку по отсечению не оптимальных ветвей решения, скорость увеличилась на порядок К сообщению приложен файл: __2.rar(43Kb)
Здравствуйте! У меня возникла проблема: попробовал найти все комбинации из 6 чисел, из диапазона от 1 до 49, для заданных сумм методом ограниченного перебора. Уже на сумме в 104 excel ругается "Run-time error '1004': Application -defined or object-defined error" Ссылается на строчку: Range("F1").Offset(j - 1, 0) = "'" & txt Видимо, не хватает ячеек в столбце. Подскажете, пожалуйста, как исправить, чтобы результаты продолжали выводиться в следующий столбец на этой же или на другой странице?
MCH,
Цитата
Доработал свой макрос с ограниченным перебором. Сделал дополнительную проверку по отсечению не оптимальных ветвей решения, скорость увеличилась на порядок К сообщению приложен файл: __2.rar(43Kb)
Здравствуйте! У меня возникла проблема: попробовал найти все комбинации из 6 чисел, из диапазона от 1 до 49, для заданных сумм методом ограниченного перебора. Уже на сумме в 104 excel ругается "Run-time error '1004': Application -defined or object-defined error" Ссылается на строчку: Range("F1").Offset(j - 1, 0) = "'" & txt Видимо, не хватает ячеек в столбце. Подскажете, пожалуйста, как исправить, чтобы результаты продолжали выводиться в следующий столбец на этой же или на другой странице?Akeron
Файл в первом (и шестом) посте сохранен в формате Ex2003, а значит на лист в один столбец поместится не более 65536 значений, сохраните файл в формате xlsm или xlsb, после его открытия в листе будет более 1млн строк. Так для суммы 104 существует 66389 вариантов сложения шести слагаемых от 1 до 49. Всего различных сочетаний 6 из 49: ЧИСЛКОМБ(49;6) = 13983816, поэтому 1млн строк вполне достаточно, чтобы получить все комбинации сумм от 21 (1+2+3+4+5+6) до 279 (49+48+47+46+45+44). Так сумму 150 можно получить 165772 вариантами
Сделал частотный анализ сумм чисел "6 из 49"
Файл в первом (и шестом) посте сохранен в формате Ex2003, а значит на лист в один столбец поместится не более 65536 значений, сохраните файл в формате xlsm или xlsb, после его открытия в листе будет более 1млн строк. Так для суммы 104 существует 66389 вариантов сложения шести слагаемых от 1 до 49. Всего различных сочетаний 6 из 49: ЧИСЛКОМБ(49;6) = 13983816, поэтому 1млн строк вполне достаточно, чтобы получить все комбинации сумм от 21 (1+2+3+4+5+6) до 279 (49+48+47+46+45+44). Так сумму 150 можно получить 165772 вариантами
Всем привет! Подниму старую тему : столкнулся с задачей о сумме подмножеств с но выбором суммандов не более одного из каждой группы. При этом, необходимо перебрать и сохранить все возможные варианты получения суммы. У Михаила (MCH) есть функция LimitBruteForce - которая перебирает все возможные варианты, но в рамках одной группы. В принципе это то, что нужно, просто каждому члену суммы поставить индекс принадлежности к группе и потом отсеять выборки, в которых будут встречаться два одинаковых индекса группы... Но, мне кажется, можно это сделать более оптимальным способом (т.к. на 10 группах из 20 членов, если их собрать в одно множество в 200 членов, тратится уже значительное время). Просьба указать путь истинный, как доработать LimitBruteForce или может иной алгоритм под эту задачу... (результатом должны быть все возможные комбинации, для которых сумма будет лежать в пределах погрешности от искомой) Прикрепляю файл с примером групп слагаемых: Заранее большое спасибо, у меня уже полтора дня затуп по этой теме...
Всем привет! Подниму старую тему : столкнулся с задачей о сумме подмножеств с но выбором суммандов не более одного из каждой группы. При этом, необходимо перебрать и сохранить все возможные варианты получения суммы. У Михаила (MCH) есть функция LimitBruteForce - которая перебирает все возможные варианты, но в рамках одной группы. В принципе это то, что нужно, просто каждому члену суммы поставить индекс принадлежности к группе и потом отсеять выборки, в которых будут встречаться два одинаковых индекса группы... Но, мне кажется, можно это сделать более оптимальным способом (т.к. на 10 группах из 20 членов, если их собрать в одно множество в 200 членов, тратится уже значительное время). Просьба указать путь истинный, как доработать LimitBruteForce или может иной алгоритм под эту задачу... (результатом должны быть все возможные комбинации, для которых сумма будет лежать в пределах погрешности от искомой) Прикрепляю файл с примером групп слагаемых: Заранее большое спасибо, у меня уже полтора дня затуп по этой теме...3N4
Всем привет, нужна помощь с макросом (взят с форума). Есть массив BP:CA, из цифр в столбце BV подбираются значения, сумма которых указана в ячейке D5. Потом макрос переносит подобранные значения в столбец Р. Мне нужно что бы макрос переносил всю строку массива, как показано в примере J14:U20. И очищал те которые взял в массиве BP:CA (т.е. № п/п4,5,6 должен быть очищен). Спасибо за любую помощь и подсказки.
Всем привет, нужна помощь с макросом (взят с форума). Есть массив BP:CA, из цифр в столбце BV подбираются значения, сумма которых указана в ячейке D5. Потом макрос переносит подобранные значения в столбец Р. Мне нужно что бы макрос переносил всю строку массива, как показано в примере J14:U20. И очищал те которые взял в массиве BP:CA (т.е. № п/п4,5,6 должен быть очищен). Спасибо за любую помощь и подсказки.serjj22
MCH, Добрый день! по этой теме: http://www.excelworld.ru/forum/10-5196-1 Подбор слагаемых под нужную сумму Подскажите пожалуйста, что нужно изменить в вашем макросе, чтобы уже выбранные числа больше в расчет не попадали спасибо!
MCH, Добрый день! по этой теме: http://www.excelworld.ru/forum/10-5196-1 Подбор слагаемых под нужную сумму Подскажите пожалуйста, что нужно изменить в вашем макросе, чтобы уже выбранные числа больше в расчет не попадали спасибо!dude
Во вложении решение задачи по подбору множителей под нужное произведение. В основе решения перебор, сделанный на базе задачи "сумма подмножеств" из первого сообщения.
Во вложении решение задачи по подбору множителей под нужное произведение. В основе решения перебор, сделанный на базе задачи "сумма подмножеств" из первого сообщения.MCH
MCH, добрый день. Можно вопрос: В задаче все решения начинаются с наибольшего показателя. Возможно ли решение где будут учтены абсолютно все решения, начинающиеся с разных показателей?
MCH, добрый день. Можно вопрос: В задаче все решения начинаются с наибольшего показателя. Возможно ли решение где будут учтены абсолютно все решения, начинающиеся с разных показателей?Aselisa1629
Задача: набрать максимальную сумму из любого количества чисел максимально набираемую сумму например 10000, но не на сколько не большую ее. Например есть покупки: 3439 7325 15810 6000 2520 2500 2645
Банк готов вернуть заданную сумму 10000 р но не более Найти наборы чисел которые максимально наберут наибольшую сумму.
Задача: набрать максимальную сумму из любого количества чисел максимально набираемую сумму например 10000, но не на сколько не большую ее. Например есть покупки: 3439 7325 15810 6000 2520 2500 2645
Банк готов вернуть заданную сумму 10000 р но не более Найти наборы чисел которые максимально наберут наибольшую сумму.autostavrroute
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
