Распределение сумм по группам (математическая задачка)
Дано много сумм, их надо разложить на строго определенные "кучки" сумм. Лучше на примере:
Даны цифры: 1, 1, 7, 4, 2, 1
Их нужно разложить на "кучки": 1)7, 2)3, 3)6.
Понятно, что в 1-ую кучку попадёт 7, во 2-ую 2 и 1, в 3-ю: 1, 1 и 4!
Но это лёгкая задача, у меня на самом деле сумм больше, они не все целые и "кучек" тоже много. Возможны несколько вариантов распределения, но мне интересен любой правильный (первый попавшийся). Возможно, что решения вообще нет (например в указанном примере я кучки сделаю дробные, с десятыми).
Нашёл примерно то что нужно: , но когда чисел много он считает слишком долго (часами). Можно самому придумать алгоритм (например тупым пересчётом), но на больших количествах чисел он явно засядет на сутки подсчётов...
Вряд ли на 1С что-то подобное уже реализовано, но может есть что-то готовое, например, в Excele? Какой-нибудь поиск решений?
Даны цифры: 1, 1, 7, 4, 2, 1
Их нужно разложить на "кучки": 1)7, 2)3, 3)6.
Понятно, что в 1-ую кучку попадёт 7, во 2-ую 2 и 1, в 3-ю: 1, 1 и 4!
Но это лёгкая задача, у меня на самом деле сумм больше, они не все целые и "кучек" тоже много. Возможны несколько вариантов распределения, но мне интересен любой правильный (первый попавшийся). Возможно, что решения вообще нет (например в указанном примере я кучки сделаю дробные, с десятыми).
Нашёл примерно то что нужно: , но когда чисел много он считает слишком долго (часами). Можно самому придумать алгоритм (например тупым пересчётом), но на больших количествах чисел он явно засядет на сутки подсчётов...
Вряд ли на 1С что-то подобное уже реализовано, но может есть что-то готовое, например, в Excele? Какой-нибудь поиск решений?
По теме из базы знаний
Найденные решения
Вот обработка, построенная на основе задачи 23 - функции метода ветвей и границ из .
Она, правда, находит именно минимальное количество отгрузок для составления суммы счета-фактуры и только одной суммы. Но, во-первых, можно применять ее последовательно, а, во-вторых, можно и подработать ее с целью вывода всех вариантов.
В целевой функции там еще было зашито использование минимального разнообразия кусков (отгрузок). Наверное, это ограничение нужно будет ослабить.
Во всяком случае суммы из файла она из исходных чисел составляет за секунды-минуты.
Она, правда, находит именно минимальное количество отгрузок для составления суммы счета-фактуры и только одной суммы. Но, во-первых, можно применять ее последовательно, а, во-вторых, можно и подработать ее с целью вывода всех вариантов.
В целевой функции там еще было зашито использование минимального разнообразия кусков (отгрузок). Наверное, это ограничение нужно будет ослабить.
Во всяком случае суммы из файла она из исходных чисел составляет за секунды-минуты.
Прикрепленные файлы:
Рюкзак.erf
Остальные ответы
Подписаться на ответы
Инфостарт бот
Сортировка:
Древо развёрнутое
Свернуть все
(1) klinval, скажите: сколько примерно чисел (сумм) и сколько примерно групп (кучек)? Какой диапазон изменения чисел? А также: какую конкретную практическую задачу вы таким образом пытаетесь решить? (дело в том, что конкретную задачу решать гораздо интереснее, чем абстрактную)
(2) ildarovich,
Чисел от 50 до 1000 (примерно). Кучек от 3 до 20.
От пару тысяч рублей до 100 000.
Есть перечень отправок товаров. Напротив каждой отправки стоит сумма. По этому перечню сформированы N счет-фактур. Непонятно какая строка в какую СФ попала. Мы выступаем агентом и нам так дали и не расшифровали (такой контрагент). Сейчас нужно хоть как-то логически распределить.
сколько примерно чисел (сумм) и сколько примерно групп (кучек)?
Чисел от 50 до 1000 (примерно). Кучек от 3 до 20.
Какой диапазон изменения чисел?
От пару тысяч рублей до 100 000.
А также: какую конкретную практическую задачу вы таким образом пытаетесь решить? (дело в том, что конкретную задачу решать гораздо интереснее, чем абстрактную)
Есть перечень отправок товаров. Напротив каждой отправки стоит сумма. По этому перечню сформированы N счет-фактур. Непонятно какая строка в какую СФ попала. Мы выступаем агентом и нам так дали и не расшифровали (такой контрагент). Сейчас нужно хоть как-то логически распределить.
Возможно есть какой-то математический алгоритм, который на 300 числах не будет зависать часами как , а хотя бы минут за 10 выполнит вычисления?
(7) starik-2005, спасибо за ссылку, сейчас почитаю.
(8) ildarovich,
Сам когда только столкнулся с этой задачей пришёл к выводу, что программно я будут очень долго искать, поэтому стал делать руками. Сейчас просто надоело. Уже день отсидел пялясь в таблицы Excel и пытаясь увидеть логику распределения. Поэтому опять начала посещать мысль, что может лучше день попрограммировать, но боюсь, что результата не будет... А нужно как всегда срочно и не хочется день потратить впустую. Поэтому и спрашиваю совета.
У меня есть идея частично использовать алгоритм из: , но после каждого этапа запускать N фоновых заданий. Т.е. я формирую диапазон возможных сумм из 1 числа. Для примера из (9) это будут: 40 000,00; 40 500,00; 14 000,00; 22 800,00; 22 500,00. Далее запускаю 5 фоновых заданий. Потом каждое фоновое задание делает свой возможный вариант из 2-х чисел используя первое только свое определенное. Уникальных вариантов получится N. Далее запускается опять N фоновых заданий и т.д. Пока не знаю как это реализовать, но боюсь когда реализую тупо повешу сервер 100500 фоновыми заданиями и нечего не добьюсь.
Посмотрел сейчас на все 9 файлов: кучек больше 8 в них нет. У этого контрагента по 1 отчету вряд-ли будет больше 10 СФ, поэтому зря я написал от 3 до 20... Скорее от 2 до 10 групп.
(10) starik-2005, суммы всегда близкие. Если выбрать различные суммы даже на 1000 строк я думаю будет не больше 15 различных.
(8) ildarovich,
Навскидку, пространство для перебора настолько велико: ~ 2^1000, что чисто переборные методы не то, что за дни - за время жизни вселенной решения не найдут.
Сам когда только столкнулся с этой задачей пришёл к выводу, что программно я будут очень долго искать, поэтому стал делать руками. Сейчас просто надоело. Уже день отсидел пялясь в таблицы Excel и пытаясь увидеть логику распределения. Поэтому опять начала посещать мысль, что может лучше день попрограммировать, но боюсь, что результата не будет... А нужно как всегда срочно и не хочется день потратить впустую. Поэтому и спрашиваю совета.
У меня есть идея частично использовать алгоритм из: , но после каждого этапа запускать N фоновых заданий. Т.е. я формирую диапазон возможных сумм из 1 числа. Для примера из (9) это будут: 40 000,00; 40 500,00; 14 000,00; 22 800,00; 22 500,00. Далее запускаю 5 фоновых заданий. Потом каждое фоновое задание делает свой возможный вариант из 2-х чисел используя первое только свое определенное. Уникальных вариантов получится N. Далее запускается опять N фоновых заданий и т.д. Пока не знаю как это реализовать, но боюсь когда реализую тупо повешу сервер 100500 фоновыми заданиями и нечего не добьюсь.
Брут-форс-методы (перебор) где-то для 40 чисел - 10 кучек могут работать, а больше.... вряд-ли.
Посмотрел сейчас на все 9 файлов: кучек больше 8 в них нет. У этого контрагента по 1 отчету вряд-ли будет больше 10 СФ, поэтому зря я написал от 3 до 20... Скорее от 2 до 10 групп.
(10) starik-2005, суммы всегда близкие. Если выбрать различные суммы даже на 1000 строк я думаю будет не больше 15 различных.
(13) klinval, а там в один проход все делается - достаточно накодить в экселе: упорядочиваете первый столбик, дальше суммируете его до момента, пока не превысите первую сумму. Превысили - вычитаете последнее и находите следующее, меньше чем оставшаяся часть. Ну и так далее. Минутное дело - сразу будет понятно, на сколько эффективно.
(14) starik-2005, может я конечно что-то не понял, но скорее всего жадный алгоритм не подойдёт, а вот рюкзак думаю будет в самый раз (или рюкзак и жадный алгоритм это одно и тоже?). Как я понял у меня для примера (9) будет 422 строчки и 3 столбца... Надо на работе опробовать на практике, хотя бы не универсально, а на одном примере, чтобы понять будет ли толк.
\\\\\
Столбцов всё-таки будет <Число которое хотим получить>\<минимальное число из набора>. Т.е. для примера (9) для группы 1459800 - это будет 1459800\14000 = 105 столбцов с шагом 14000 (последний шаг будет меньше).
Проблема в этом методе в том, что я могу использовать в 1 группе какой-то набор чисел, который я должен был приберечь для последующих групп. Например первая группа у меня единственная целая, другие с десятыми. Если я в первую группу помещу все числа с десятыми, то задача математически станет не решаемой...
Короче надо завтра подумать как это обойти...
\\\\\
Столбцов всё-таки будет <Число которое хотим получить>\<минимальное число из набора>. Т.е. для примера (9) для группы 1459800 - это будет 1459800\14000 = 105 столбцов с шагом 14000 (последний шаг будет меньше).
Проблема в этом методе в том, что я могу использовать в 1 группе какой-то набор чисел, который я должен был приберечь для последующих групп. Например первая группа у меня единственная целая, другие с десятыми. Если я в первую группу помещу все числа с десятыми, то задача математически станет не решаемой...
Короче надо завтра подумать как это обойти...
(6) klinval, спасибо, пока понятно: нужно распределить отправки (50-1000) по счет-фактурам (3-20), чтобы сошлись суммы.
Навскидку, пространство для перебора настолько велико: ~ 2^1000, что чисто переборные методы не то, что за дни - за время жизни вселенной решения не найдут. Нужно подумать, можно ли перебор сократить. Брут-форс-методы (перебор) где-то для 40 чисел - 10 кучек могут работать, а больше.... вряд-ли.
Навскидку, пространство для перебора настолько велико: ~ 2^1000, что чисто переборные методы не то, что за дни - за время жизни вселенной решения не найдут. Нужно подумать, можно ли перебор сократить. Брут-форс-методы (перебор) где-то для 40 чисел - 10 кучек могут работать, а больше.... вряд-ли.
На самом деле файликов для распределения было изначально немного и я их руками распределил. Обычно там из-за специфики работы можно часть сумм чисто логически кинуть на одну СФ, а иногда распределение просто по порядку идёт, иногда можно сгруппировать на одинаковые суммы и они очень хорошо делятся на группы... Пару раз помог себе допиленной обработкой из . Иногда сразу было видно, что математически задачу не решить.
Сейчас у меня появилось ещё 9 файлов для распределения (разной сложности). Если этим заниматься вручную уйдёт от 4 часов до 10 (примерно). Вот я и подумал, что может всё-таки можно как-то это сделать быстрее чем вручную.
Один такой файл я частично распределил, не распределенные суммы скинул для примера во вложении. Есть вероятность, что в примере вообще нереально распределить на группы: 1 459 800,00; 2 941 300,00; 7 345 700,00
Сейчас у меня появилось ещё 9 файлов для распределения (разной сложности). Если этим заниматься вручную уйдёт от 4 часов до 10 (примерно). Вот я и подумал, что может всё-таки можно как-то это сделать быстрее чем вручную.
Один такой файл я частично распределил, не распределенные суммы скинул для примера во вложении. Есть вероятность, что в примере вообще нереально распределить на группы: 1 459 800,00; 2 941 300,00; 7 345 700,00
Прикрепленные файлы:
Пример сумм для распределения.xlsx
(9) klinval, с такими близкими суммами, как в эксельке, у Вас может вполне нормально отработать жадный алгоритм. Если характер сумм с частыми повторениями является постоянной особенностью, то жадный алгоритм с последующей дооптимизацией вполне может дать приемлемый результат. А что не получилось - из остаточных цифр пересобирать.
(27) klinval, я не знаю, как этот алгоритм называется в научных кругах
просто написал
ссылко и публикаций не знаю (тех, что здесь приведены - не смотрел)
является ли алгоритм секретом, тоже не знаю, я его таковым не объявлял :)))
"поделитцо" пока не могу, потому что есть моменты, которые надо тонко подпихнуть
когда и если сделаю это, вы узнаете первым :))
просто написал
ссылко и публикаций не знаю (тех, что здесь приведены - не смотрел)
является ли алгоритм секретом, тоже не знаю, я его таковым не объявлял :)))
"поделитцо" пока не могу, потому что есть моменты, которые надо тонко подпихнуть
когда и если сделаю это, вы узнаете первым :))
Вот обработка, построенная на основе задачи 23 - функции метода ветвей и границ из .
Она, правда, находит именно минимальное количество отгрузок для составления суммы счета-фактуры и только одной суммы. Но, во-первых, можно применять ее последовательно, а, во-вторых, можно и подработать ее с целью вывода всех вариантов.
В целевой функции там еще было зашито использование минимального разнообразия кусков (отгрузок). Наверное, это ограничение нужно будет ослабить.
Во всяком случае суммы из файла она из исходных чисел составляет за секунды-минуты.
Она, правда, находит именно минимальное количество отгрузок для составления суммы счета-фактуры и только одной суммы. Но, во-первых, можно применять ее последовательно, а, во-вторых, можно и подработать ее с целью вывода всех вариантов.
В целевой функции там еще было зашито использование минимального разнообразия кусков (отгрузок). Наверное, это ограничение нужно будет ослабить.
Во всяком случае суммы из файла она из исходных чисел составляет за секунды-минуты.
Прикрепленные файлы:
Рюкзак.erf
(16) ildarovich, огромное спасибо за обработку! Честно пока не понял как она работает, но главное работает))
Ваше представление задачи именно в таком виде побудило меня на другой вариант поиска, через систему линейных уравнений. Составляем уравнения:
14 000 * А1 + 22 500 * Б1 + 22 800 * В1 + 40 000 * Г1 + 40 500 * Д1 = 1 459 800
14 000 * А2 + 22 500 * Б2 + 22 800 * В2 + 40 000 * Г2 + 40 500 * Д2 = 7 345 700
14 000 * А3 + 22 500 * Б3 + 22 800 * В3 + 40 000 * Г3 + 40 500 * Д3 = 2 941 300
А1 + А2 + А3 = 1
Б1 + Б2 + Б3 = 17
В1 + В2 + В3 = 281
Г1 + Г2 + Г3 = 76
Д1 + Д2 + Д3 = 47
Скармливаем их Excel и через поиск решений находим готовое решение через симплекс метод. См. результат в Excel. Задачу Excel решал около 10-20 минут.
Думаю дальше решать задачу параллельно сразу 2 методами (через Excel и через обработку ildarovich из (16)).
Ваше представление задачи именно в таком виде побудило меня на другой вариант поиска, через систему линейных уравнений. Составляем уравнения:
14 000 * А1 + 22 500 * Б1 + 22 800 * В1 + 40 000 * Г1 + 40 500 * Д1 = 1 459 800
14 000 * А2 + 22 500 * Б2 + 22 800 * В2 + 40 000 * Г2 + 40 500 * Д2 = 7 345 700
14 000 * А3 + 22 500 * Б3 + 22 800 * В3 + 40 000 * Г3 + 40 500 * Д3 = 2 941 300
А1 + А2 + А3 = 1
Б1 + Б2 + Б3 = 17
В1 + В2 + В3 = 281
Г1 + Г2 + Г3 = 76
Д1 + Д2 + Д3 = 47
Скармливаем их Excel и через поиск решений находим готовое решение через симплекс метод. См. результат в Excel. Задачу Excel решал около 10-20 минут.
Думаю дальше решать задачу параллельно сразу 2 методами (через Excel и через обработку ildarovich из (16)).
Прикрепленные файлы:
(17) klinval, здорово, тоже хотел попробовать симплекс-метод, но там есть риск получить не целочисленные решения. Думал, как это обойти. Придется, видимо, по ходу решения ограничения добавлять. У меня есть своя реализация симплекс-метода, интересно будет сравнить его по скорости c Эксель. Спасибо за задачу!
(18) ildarovich,
В excele в поиске решений можно ограничить результат целыми числами (см. вложение).
Я когда то курсовую сдавал: программировал реализацию М-метода на Delphi... Правда уже абсолютно ничего не помню, т.к. в реальной жизни с чистой математикой практически не сталкивался, в основном бух. учёт, который вроде как должен быть точной наукой, но на самом деле не всегда так получается :)
Да мне то за что? Это вам спасибо!
здорово, тоже хотел попробовать симплекс-метод, но там есть риск получить не целочисленные решения.
В excele в поиске решений можно ограничить результат целыми числами (см. вложение).
У меня есть своя реализация симплекс-метода, интересно будет сравнить его по скорости c Эксель.
Я когда то курсовую сдавал: программировал реализацию М-метода на Delphi... Правда уже абсолютно ничего не помню, т.к. в реальной жизни с чистой математикой практически не сталкивался, в основном бух. учёт, который вроде как должен быть точной наукой, но на самом деле не всегда так получается :)
Спасибо за задачу!
Да мне то за что? Это вам спасибо!
Прикрепленные файлы:
Рассказываю что всё-таки мне помогло: частично воспользовался отчетом из (16), частично поиском решений Excel, но в большинстве случаев ручное распределение, т.к. чуть меньше половины были нераспределяемые. Возможно мне пригодился бы в таком случае алгоритм из для нахождения максимально приближенного решения, но его было просто некогда реализовывать (да и искать одновременно решение 4 способами слишком трудозатратно).
Перечислю способы (+-):
1. Отчет ildarovich из (16) сообщения:
+ быстро понимает что сумма не распределяется
+ быстро находит решение
- иногда возможны не распределенные суммы, хотя их можно распределить. См. прикрепленные файлы: Excel смог найти решение, а отчет нет.
2. Excel поиск решений:
+ cразу находит готовое решение (в какую СФ какую сумму определить)
- долго забивать данные, долго искать
- вообще не понимает когда решение найти нереально. Оставил часов на 6 искать решение, он честно перебирал. Потом решил поискать ручками - логически понял, что задача нерешаема. Excel же похоже решал бы её до бесконечности...
3. Ручной способ
+ быстрее Excel понимаешь, что сумма не распределяется. На некоторых наборах данных можно быстрее 1-го способа понять, что распределить нереально.
+ на некоторых наборах данных запросто обгоняешь 2 других способа.
+ нераспределяемые суммы проще распределить этим способом.
- приходится целый день распределять суммы вручную... Не самое приятное занятие.
- в зависимости от набора данных может оказаться дольше 1 и 2 способов.
Проще оказалось начать распределение ручками, а дальше при необходимости и возможности (т.е. когда задача теоретически решаема) задействовать 1 или 2 способы.
Перечислю способы (+-):
1. Отчет ildarovich из (16) сообщения:
+ быстро понимает что сумма не распределяется
+ быстро находит решение
- иногда возможны не распределенные суммы, хотя их можно распределить. См. прикрепленные файлы: Excel смог найти решение, а отчет нет.
2. Excel поиск решений:
+ cразу находит готовое решение (в какую СФ какую сумму определить)
- долго забивать данные, долго искать
- вообще не понимает когда решение найти нереально. Оставил часов на 6 искать решение, он честно перебирал. Потом решил поискать ручками - логически понял, что задача нерешаема. Excel же похоже решал бы её до бесконечности...
3. Ручной способ
+ быстрее Excel понимаешь, что сумма не распределяется. На некоторых наборах данных можно быстрее 1-го способа понять, что распределить нереально.
+ на некоторых наборах данных запросто обгоняешь 2 других способа.
+ нераспределяемые суммы проще распределить этим способом.
- приходится целый день распределять суммы вручную... Не самое приятное занятие.
- в зависимости от набора данных может оказаться дольше 1 и 2 способов.
Проще оказалось начать распределение ручками, а дальше при необходимости и возможности (т.е. когда задача теоретически решаема) задействовать 1 или 2 способы.
Прикрепленные файлы:
(20) Информация для меня интересная. Тем, что в этих задачах первым на ум приходит динамическое программирование, по сути, сокращенный перебор. Про метод Гомори (развитие симплекс-метода на случай целочисленных переменных) почему-то вспоминают не часто, хотя он должен иметь гораздо меньшую трудоемкость (на приведенных примерах). А я как раз ищу примеры задач под свою реализацию симплекс-метода (правда, для Гомори еще потребуется отсечения доделывать). И пример этой задачи очень кстати. Два набора чисел для решения тут уже есть. Еще бы штуки три набора посложнее для отладки. Правда, сейчас пока некогда заниматься, но на будущее бы пригодилось.
(22) ildarovich, могу дать интересный пример, который руками распределить намного быстрее чем программно:
Дано:
А) 405 чисел по 30 000
Б) 109 чисел по 31 000
В) 1670 чисел по 37 000
Нужно из них составить:
14 490 000
38 390 500
341 000
442 500
14 995 000
8 660 000
Фактически это система уравнений:
30 000 * А1 + 31 000 * Б1 + 37 000 * В1 = 14 490 000
30 000 * А2 + 31 000 * Б2 + 37 000 * В2 = 38 390 500
30 000 * А3 + 31 000 * Б3 + 37 000 * В3 = 341 000
30 000 * А4 + 31 000 * Б4 + 37 000 * В4 = 442 500
30 000 * А5 + 31 000 * Б5 + 37 000 * В5 = 14 995 000
30 000 * А6 + 31 000 * Б6 + 37 000 * В6 = 8 660 000
А1+А2+А3+А4+А5+А6 = 405
Б1+Б2+Б3+Б4+Б5+Б6 = 109
В1+В2+В3+В4+В5+В6 = 1670
Если подумать логически: распределить нереально, т.к. присутствуют числа не нулевым 3 разрядом числа, а числа из которых нужно составить все до 3 разряда нулевые! В случае когда нельзя распределить нужно распределить те которые распределяются, другие сделать примерно равными.
Например ваша обработка из этих чисел составлять 14 490 000 будет долго, а логически это решить легко и быстро: выделяем в Excele суммы 37 000 чтобы получилось больше или равно 14 490 000. У нас это 406 чисел которые дают 15 022 000, что на 32 больше чем нужно. Значит нам нужно вместо 2 чисел по 37000 взять 2 по 30000 и вместо 3 чисел по 37000 берём 3 по 30000. Итого получается 37000*401+30000*2+31000*3...
Чтобы пример стал распределяемым можно его переделать на:
А) 405 чисел по 30 000
Б) 109 чисел по 31 000
В) 1670 чисел по 37 000
Г) 1 число 21 500
Д) 1 число 35 500
Е) 1 число 48 000
Дано:
А) 405 чисел по 30 000
Б) 109 чисел по 31 000
В) 1670 чисел по 37 000
Нужно из них составить:
14 490 000
38 390 500
341 000
442 500
14 995 000
8 660 000
Фактически это система уравнений:
30 000 * А1 + 31 000 * Б1 + 37 000 * В1 = 14 490 000
30 000 * А2 + 31 000 * Б2 + 37 000 * В2 = 38 390 500
30 000 * А3 + 31 000 * Б3 + 37 000 * В3 = 341 000
30 000 * А4 + 31 000 * Б4 + 37 000 * В4 = 442 500
30 000 * А5 + 31 000 * Б5 + 37 000 * В5 = 14 995 000
30 000 * А6 + 31 000 * Б6 + 37 000 * В6 = 8 660 000
А1+А2+А3+А4+А5+А6 = 405
Б1+Б2+Б3+Б4+Б5+Б6 = 109
В1+В2+В3+В4+В5+В6 = 1670
Если подумать логически: распределить нереально, т.к. присутствуют числа не нулевым 3 разрядом числа, а числа из которых нужно составить все до 3 разряда нулевые! В случае когда нельзя распределить нужно распределить те которые распределяются, другие сделать примерно равными.
Например ваша обработка из этих чисел составлять 14 490 000 будет долго, а логически это решить легко и быстро: выделяем в Excele суммы 37 000 чтобы получилось больше или равно 14 490 000. У нас это 406 чисел которые дают 15 022 000, что на 32 больше чем нужно. Значит нам нужно вместо 2 чисел по 37000 взять 2 по 30000 и вместо 3 чисел по 37000 берём 3 по 30000. Итого получается 37000*401+30000*2+31000*3...
Чтобы пример стал распределяемым можно его переделать на:
А) 405 чисел по 30 000
Б) 109 чисел по 31 000
В) 1670 чисел по 37 000
Г) 1 число 21 500
Д) 1 число 35 500
Е) 1 число 48 000
(20) klinval, лично я бы сделал два варианта всего:
1. Жадный алгоритм с последующими перестановками. Отрабатывает очень быстро, но, конечно, может и не дать нужного результата. Но если он нашел результат, то сделал это очень быстро.
2. Рюкзак - ищет лучший результат для имеющихся данных. Его нужно реализовать с шагом таблицы для всех НОД (алгебра, 5-й класс, если не 4-й, , адаптировать его для копеек можно, умножив числа на 100, если кто не в курсе).
1. Жадный алгоритм с последующими перестановками. Отрабатывает очень быстро, но, конечно, может и не дать нужного результата. Но если он нашел результат, то сделал это очень быстро.
2. Рюкзак - ищет лучший результат для имеющихся данных. Его нужно реализовать с шагом таблицы для всех НОД (алгебра, 5-й класс, если не 4-й, , адаптировать его для копеек можно, умножив числа на 100, если кто не в курсе).
Внимание! Тема сдана в архив
Для получения уведомлений об ответах подключите телеграм бот:
Инфостарт бот