Форум на Исходниках.RU

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Tue, 17 Jun 2014 10:39:28 +0000

Swetlana:

Цитата Swetlana @ 29.04.13, 14:19

вот ещё одна задачка на набор сумм или одномерную упаковку
<...>

Дипломница защитилась, бухгалтерская программа для закупок университетом всякой всячины. Прямо на защите от членов ГЭК поступили предложения о покупке программы.

Математическая составляющая - набиралась заданная сумма с заданным допустимым отклонением из заданных слагаемых. Размерность сверхбольшая, слагаемые целые положительные, набирали миллионы из нескольких сотен слагаемых, копейки округляли до рублей. Хороший приближённый алгоритм получился, точный и быстрый, абсолютная погрешность посчитана, относительная асимптотическая равна 1. Удивительно было бы, если бы не получился, столько лет я этими наборами сумм на сорцах занималась :D
Как статью опубликуем (на английском), выложу здесь и статью, и подробное описание алгоритма.

Добавлено 17.06.14, 10:48
Да, выч. сложность - O(n³), где n - количество слагаемых и не зависит от размера суммы.
Основная идея - рекурсивно вызывался FFD с некоторыми хитростями, пока не оставалось 20 слагаемых, заием сумма мгновенно добиралась точным алгоритмом (алгоритмом с возвратом). Время работы точного для фиксированного кол-ва слагаемых, само собой, в выч. сложность не входит.
И ещё массив слагаемых встряхивали и снова алгоритм запускали. Оно особо и не надо, и на одном запуске хорошо работало, но при O(n³) можно себе позволить.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Rate93 — Thu, 23 May 2013 08:42:48 +0000

Rate93:

Цитата MBo @ 23.05.13, 05:47

Ну как - если в массиве T ячейки с индексами Ves0-D..Ves0+D пусты, то сумму с таким допуском (+-) не набрать

Так а размерность массива T[0..N,0..Ves0+D], как понимать фразу

Цитата

если в массиве T ячейки с индексами Ves0-D..Ves0+D пусты

Сумма чисел в массиве, наиболее приближающаяся к необходимой

MBo — Thu, 23 May 2013 05:47:50 +0000

MBo: Ну как - если в массиве T ячейки с индексами Ves0-D..Ves0+D пусты, то сумму с таким допуском (+-) не набрать

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Rate93 — Thu, 23 May 2013 05:42:10 +0000

Rate93: Извиняюсь за вопрос, вроде всё элементарно, просто поиск слагаемых завёл под условие

if (Ves0 - D <= sum <= Ves0 + D)

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Rate93 — Thu, 23 May 2013 04:41:54 +0000

Rate93: Но возникла проблема, встречаются суммы округлённые до сотых, соответственно появляется допуск (применительно к использованному алгоритму D=10, т.к. исходные числа домножаю на 1000). Так вот теперь такая проблема: как доработать алгоритм, чтобы поиск слагаемых не осуществлялся если найденная сумма -/+ допуск не ровна данной сумме?

Приведу алгоритм Swetlana ещё раз:

const N=4;

Ves0=25;

D=2;

var

M: array[1..N]of integer;

T:array[0..N,0..Ves0+D]of byte;

Ves,sum,i,j,dmin:integer;

begin

Ves:=Ves0+D;

M[1]:= 18; M[2]:= 4; M[3]:= 4; M[4]:= 4;

T[0,0]:=1;

for j := 1 to Ves do T[0, j] := 0;

for i := 1 to N do T[i, 0] := 1;

for i := 1 to N do begin

for j := 1 to Ves do begin

if j >= M[i] then begin

if T[i - 1, j]> T[i - 1, j - M[i]] then

T[i,j]:= T[i - 1, j]

else T[i, j]:= T[i - 1, j - M[i]];end

else T[i, j]:= T[i - 1, j];

end;

dmin:=Ves; sum:=0;

for j:=Ves downto 1 do

if T[N, j] = 1 then

if dmin>abs(Ves0-j) then

begin dmin:=abs(Ves0-j); sum:=j; end;

writeln('Sum=',sum,' dmin=',dmin);

for i := N downto 1 do

begin

if T[i, sum] = T[i - 1, sum] then

writeln (i, '---No')

else

begin writeln (i, ' ',M[i]);

sum := sum - M[i];

end;

readln;

end.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Rate93 — Thu, 23 May 2013 04:21:29 +0000

Rate93: В общем применил алгоритм описанный в посте 29, для 25 слагаемых и 7-значной суммы работает шустро. Спасибо за код!

Сумма чисел в массиве, наиболее приближающаяся к необходимой

MBo — Tue, 21 May 2013 07:41:16 +0000

MBo: сложность перебора 2^N
динамического программирования N * Sum
Вот, исходя из параметров, и надо выбирать метод.

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Rate93 — Tue, 21 May 2013 07:17:20 +0000

Rate93: >Кстати, какое реальное количество?

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

MBo — Tue, 21 May 2013 06:53:51 +0000

MBo: >слагаемых любое количество.
Кстати, какое реальное количество?
Если в пределах двух десятков, то будет быстрее перебрать все 2^N вариантов, поскольку динамическое программирование медленно будет работать для большой суммы

Сумма чисел в массиве, наиболее приближающаяся к необходимой

MBo — Tue, 21 May 2013 05:43:32 +0000

MBo: >Тогда можно использовать алгоритм Swetlana для подбора гирь?
В общем, да.

В этой ветке используются несколько усложненные алгоритмы для приближённого подбора.
Для точного подбора достаточно "задачи о наборе суммы"

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Rate93 — Tue, 21 May 2013 02:54:17 +0000

Rate93:

Цитата MBo @ 21.05.13, 02:39

>Какая именно?

Есть числа:

2 446,721
1 251,340
464,372
543,595

Нужно узнать какие из них составляют заданное число 1794,935. Решение всегда есть 100% и оно единственное, точность 0, слагаемых любое количество.

>числа из примера можно умножить на 1000
Спасибо, это вроде упрощает жизнь. Тогда можно использовать алгоритм Swetlana для подбора гирь?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

MBo — Tue, 21 May 2013 02:39:14 +0000

MBo: >У меня есть аналогичная задача
Какая именно?

>но числа не целые
числа из примера можно умножить на 1000

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Rate93 — Tue, 21 May 2013 01:52:46 +0000

Rate93: Здравствуйте! Почитал разных тем. Понял что задача распространённая. У меня есть аналогичная задача, но числа не целые. Нашёл кучу скриптов и макросов под Excel, работают хорошо, но мне под с++ надо ((. Помогите пожалуйста чем нибудь, лучше примером. Алгоритмы с целыми числами смотрел, но я так понимаю они мне не подходят.

Вот один из примеров:

2 446,721
1 251,340 1794,935
464,372
543,595

Решение всегда есть 100% и оно единственное, точность 0, слагаемых любое количество.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Mon, 29 Apr 2013 18:48:46 +0000

Swetlana: если ДП будет тормозить
1. вначале наиболее крупные слагаемые раскидать по набираемым суммам, чтобы значительно их уменьшить
2. добирать остатки ДП

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Mon, 29 Apr 2013 14:19:14 +0000

Swetlana: вот ещё одна задачка на набор сумм или одномерную упаковку
надо сделать постановку задачи

Имеется n предметов положительной вещественной стоимости (рубли-копеки, вообще говоря).
Имеется m контейнеров, m-1 контейнер положительной вместимости, m - безразмерный, m>=3.
Размерность большая. Предметов примерно 200, суммы большие.
Что нового - контейнеры с приоритетами. Пусть они упорядочены по убыванию приоритетов.

1. Можно назначить контейнерам какие-то веса и минимизировать взвешенную сумму отклонений. Вопрос - как приписать веса.
2. Можно набирать по отдельности, начиная с самой приоритетной суммы, но тут можно здорово промахнуться.
Какие ещё идеи?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Fri, 11 Jan 2013 06:04:55 +0000

Swetlana: поняла, что неправильно сделала постановку задачи
:( сори

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Tue, 04 Dec 2012 16:24:29 +0000

Swetlana: У вас вообще 3 варианта исходных задач.
1. Суммарный избыток = суммарная недостача. Алгоритм полностью восполняет недостачу, убирает избыток.
2. Суммарный избыток > суммарная недостача. Недостача устранена, остаток избытка остался.
3. Суммарный избыток < суммарная недостача. Избыток устранен, остаток недостачи остался.

Вы же понимаете, что решение не единственно, алгоритм построения максимального потока предлагает одно из возможных решений. :)
Если вы минимизируете количество операций с документами, то делайте "предобработку" - находите 2 документа типа
недостача = избытку и погашайте их сами. А когда таких документов не останется, запускайте построение максимального потока.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Spacer — Tue, 04 Dec 2012 15:25:48 +0000

Spacer:

Цитата Swetlana @ 23.11.12, 14:42

тогда всё решается быстро и точно алгоритмом построения максимального потока в сети

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

В моей задаче бывают случаи что среди документов с излишками и документов с недостачами встречаются документы с одинаковыми суммами.
Вполне логично было бы взять и сразу закрыть их друг на друга.
Но при решении задачи алгоритмом построения максимального потока в сети этого не происходит. Может я слишком многого хотел? :D
Документы с одинаковыми суммами не закрываются один на другой.

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Fri, 23 Nov 2012 14:42:16 +0000

Swetlana: тогда всё решается быстро и точно алгоритмом построения максимального потока в сети
я всегда пользуюсь для этого методом фаз Диница

Вначале нужно сделать сетевую постановку задачи, то есть построить граф, на котором всё будет происходить.

1. Отмечаем вершину-фиктивный источник s0, из него поток выходит.
2. Пусть у вас K документов с излишками. Берём ещё K вершин s1, ...,sk.
Соединяем фиктивный источник s0 с вершинами si, i=1..K.
Полагаем пропускную способность дуги s0->si C[s0, si] равной излишку i-го документа.
3. Отмечаем вершину фиктивный сток t0, в него поток приходит.
4. Пусть у вас R документов с недостачей. Берём ещё R вершин t1, ...,tr.
Соединяем вершины tj, j=1..R c фиктивным стоком t0.
Полагаем пропускную способность дуги tj->t0 C[tj, t0] равной недостаче j-го документа.
5. Соединяем каждую вершину-источник si со всеми вершинами-стоками tj, i=1..K; j=1..R.
Пропускные способности получившихся дуг полагаем равными +бесконечности.

Сеть построена. Теперь стандартным алгоритмом строим в сети максимальный поток из s0 в t0.
Величина потока в дугах s0->si - сколько надо забрать с i-го документа.
Величина потока в дугах tj->t0 - сколько надо добавить к j-му документу.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Spacer — Fri, 23 Nov 2012 14:15:48 +0000

Spacer:

Цитата Swetlana @ 23.11.12, 14:06

скажите, можно ли "излишек" с одного документа разделить на несколько документов с "недостачей"?

Да, можно. Я в принципе так и делаю. Вначале создаю массив из сумм документов с излишками.
После подбора решения для первого документа с недостачей корректирую массив из сумм документов с излишками и использую его при подборе решения для следующего документа с недостачей.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Fri, 23 Nov 2012 14:06:05 +0000

Swetlana: Spacer,
скажите, можно ли "излишек" с одного документа разделить на несколько документов с "недостачей"?
Например, документ1 - излишек 110 рублей.
документ2 - недостача 40 рублей, документ3 - недостача 60 рублей.
Решение: перебрасываем 60р. с документа1 на документ3 и 40р на документ2.
на документ1 остаётся излишек 10р., документы 2 и 3 - по нулям.

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Spacer — Fri, 23 Nov 2012 12:34:55 +0000

Spacer:

Цитата Swetlana @ 23.11.12, 09:38

у вас какая-то другая задача, сформулируйте, что конкретно вы хотите

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Fri, 23 Nov 2012 09:38:52 +0000

Swetlana: в #39 вы написали "набор сумм", поэтому и уточнила

слагаемые 1870, 2000, 2000; допустимое отклонение 2341
из двух вариантов 2000 (с недостатком, отклонение 341) и 3870 (с избытком, отклонение 1870)
программа выводит решение с минимальным отклонением

у вас какая-то другая задача, сформулируйте, что конкретно вы хотите

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Spacer — Fri, 23 Nov 2012 09:09:56 +0000

Spacer:

Цитата Swetlana @ 22.11.12, 16:23

дайте набор данных

Набор данных: 1870, 2000, 2000. Нужно подобрать сумму 2341.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

MBo — Thu, 22 Nov 2012 16:51:07 +0000

MBo: Алгоритм находит ближайшее решение - на таких данных решение с недостатком оказывается ближе - вот оно и выводится. Если требуется только решение с избытком, то и надо ограничить просмотр только нужной областью. Навскидку это будет:
for j:=Ves downto 1 Ves0

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Thu, 22 Nov 2012 16:23:02 +0000

Swetlana: дайте набор данных

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Spacer — Thu, 22 Nov 2012 15:49:52 +0000

Spacer:

Цитата Swetlana @ 16.08.11, 19:23

Новая версия программы. Нужно набрать 25, допустимое отклонение 2, ближайшее решение с недостатком - 22, ближайшее решение с избытком - 26, которое и выводится на печать.

Добрый день!
Я как и Сержик программист по 1С.
Запрограммировал этот алгоритм на 1С. Но натолкнулся на случай когда алгоритм не дает ближайшее решение с избытком.
Тестовые данные простейшие. Набор сумм: 1870, 2000, 2000. Нужно подобрать сумму 2341. Допустимое отклонение установил тоже 2341.
В качестве решения была подобрана одна сумма: 2000. Т.е. сумма получается с недостатком, а не с избытком.
Думал что это я неправильно перевел алгоритм на 1С. Попросил исходники которые писал Сержик.
На его исходниках получается тоже самое. В чем может быть проблема?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

amk — Thu, 09 Feb 2012 14:37:58 +0000

amk:

Цитата dmdv @ 09.02.12, 09:12

Отличие задачи о рюкзаке в том, что в ней - только сложение. В это задаче можно использовать * : + - и скобки.

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

dmdv — Thu, 09 Feb 2012 09:12:13 +0000

dmdv:

Цитата amk @ 09.02.12, 01:35

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

Тогда подробнее:

Необходимо построить выражение, значение которого будет целое число, объединяя 1 или более чисел из последовательности, используя операции сложение, вычитание, умножение, деление и скобки. Каждое число может быть использовано только 1 раз, все участвующие в расчете цифры, включая промежуточные значения, должны быть положительными натуральными числами.

Отличие задачи о рюкзаке в том, что в ней - только сложение. В это задаче можно использовать * : + - и скобки.

Ну, так значит, перебор?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Thu, 09 Feb 2012 06:17:40 +0000

Swetlana: Раз уж подняли старую тему...

Цитата Сержик @ 16.08.11, 12:50

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

Задача хорошо решается методом локального поиска Hill Climber. Хорошо значит точно и быстро.
Из статьи моего студента :)

Практическое применение алгоритма. Рассмотрим реальный пример. Стальной лист одновременно разрезается на несколько полос (штрипсов). Расстояние между резаками настраивается при помощи конечного набора втулок разной длины. Примем, что разрезаемый лист всегда шире суммарной ширины полос и нет необходимости минимизировать остатки. Таким образом, вместимость контейнеров равна ширине полос, а веса предметов равны длинам втулок. ...
С реализацией алгоритма Hill Climbing была проведена серия тестов с различным числом контейнеров m и предметов n. Проверялась скорость работы t, а так же минимальное min и максимальное max отклонение набранного веса от вместимости при фиксированном количестве начальных решений, равном 1000.
_______1.JPG (, : 676)

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Thu, 09 Feb 2012 04:10:21 +0000

Swetlana: Из трамвайного билета число 100 пытаетесь получить, расставляя знаки арифметических операций?
Но там важен порядок чисел, и каждое число обязательно используется ровно один раз.
В любом случае не знаю других способов, кроме перебора.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

amk — Thu, 09 Feb 2012 01:35:00 +0000

amk: Эта задача почти ничего общего с описанной выше не имеет.
Подозреваю, что в общем случае решается только перебором.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

dmdv — Thu, 09 Feb 2012 00:01:59 +0000

dmdv: Помогите формализовать.

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Thu, 24 Nov 2011 16:24:18 +0000

Swetlana:

Цитата Сержик @ 16.08.11, 12:50

Не отделаешься.
Набор двух сумм (разделить камни на 3 кучки равного веса) не решается за псевдополиномиальное время
http://en.wikipedia.org/wiki/Partition_problem

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Thu, 01 Sep 2011 09:41:45 +0000

Swetlana: Задача о наборе суммы минимальным числом заданных слагаемых тоже решается ДП.
Подробности здесь, сообщения №5 и №14
Набор суммы минимальным числом слагаемых

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Wed, 17 Aug 2011 10:34:41 +0000

Swetlana: Если допустимое отклонение не задано, то делаем так.
1. Устанавливаем D=0, находим решение с недостатком, запоминаем dmin - отклонение от заданной суммы.
2. Запускаем ещё раз с D=dmin-1. Если существует лучшее решение с избытком, оно будет найдено.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Tue, 16 Aug 2011 19:23:15 +0000

Swetlana: Для задачи с одной полосой.
В новой постановке ширину можно набирать хоть с недостатком, хоть с избытком, лишь бы отклонение от заданной суммы было минимальным. Для этого вводим допустимое отклонение D - насколько ширина полосы может отклониться от требований заказчика.
Ves0 - требуемая сумма, Ves=Ves0+D - максимально возможная сумма.
С помощью ДП набираем Ves, затем просматриваем набранные сумму и выбираем сумму с минимальным абсолютным отклонением.

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

Новая версия программы. Нужно набрать 25, допустимое отклонение 2, ближайшее решение с недостатком - 22, ближайшее решение с избытком - 26, которое и выводится на печать.

const N=4;

Ves0=25;

D=2;

var

M: array[1..N]of integer;

T:array[0..N,0..Ves0+D]of byte;

Ves,sum,i,j,dmin:integer;

begin

Ves:=Ves0+D;

M[1]:= 18; M[2]:= 4; M[3]:= 4; M[4]:= 4;

T[0,0]:=1;

for j := 1 to Ves do T[0, j] := 0;

for i := 1 to N do T[i, 0] := 1;

for i := 1 to N do begin

for j := 1 to Ves do begin

if j >= M[i] then begin

if T[i - 1, j]> T[i - 1, j - M[i]] then

T[i,j]:= T[i - 1, j]

else T[i, j]:= T[i - 1, j - M[i]];end

else T[i, j]:= T[i - 1, j];

end;

dmin:=Ves; sum:=0;

for j:=Ves downto 1 do

if T[N, j] = 1 then

if dmin>abs(Ves0-j) then

begin dmin:=abs(Ves0-j); sum:=j; end;

writeln('Sum=',sum,' dmin=',dmin);

for i := N downto 1 do

begin

if T[i, sum] = T[i - 1, sum] then

writeln (i, '---No')

else

begin writeln (i, ' ',M[i]);

sum := sum - M[i];

end;

readln;

end.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Сержик — Tue, 16 Aug 2011 12:50:14 +0000

Сержик: Так просто?! Щаз прогоню на реальных объемах. В ТЗ вам нужны конкретные цифры?
Спасибо!!!
Но эта задача - частный случай более глобальной проблемы...

Добавлено 16.08.11, 13:25
Да, гораздо лучше! :good:
Так вот, возникает еще такая задача:
на валу располагаются несколько ножей одновременно, т.е. рулон распускается на несколько полос(штрипсов) за один проход. Ширины полос задаются заказчиком и набираются при помощи тех же втулок как можно ближе к требуемым(можно не только слева, но и справа). Тут уж точно ДП не отделаешься?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Tue, 16 Aug 2011 12:35:31 +0000

Swetlana: Готово дело :)
Сортируйте входные данные в порядке убывания. Это будет не обязательно самое минимальное число слагаемых, но близко к минимальному.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Сержик — Tue, 16 Aug 2011 12:34:48 +0000

Сержик: Да, можно и так сказать. Не уезжайте может пока? ;) А то я тут весь в прокате, вопросов море...

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Tue, 16 Aug 2011 12:23:24 +0000

Swetlana: Сержик, т.е. если существует несколько наборов с одинаковой точностью, то нужен набор с минимальным числом слагаемых, так?
Надо было сразу сказать, а то я в Чехию чемодан укладываю, а задача хорошая, листопрокатная :)

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Сержик — Tue, 16 Aug 2011 12:10:26 +0000

Сержик: Нет, просто резчикку очевидно удобнее обойтись 3-мя, а не 50-ю. При прочих равных, разумеется.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

MBo — Tue, 16 Aug 2011 12:04:13 +0000

MBo: Есть ли реальные ограничения на количество используемых втулок?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Сержик — Tue, 16 Aug 2011 09:00:58 +0000

Сержик: Перевел на 1С, потестил на своих реальных немаленьких массивах, решение находится, весьма точно и за реальное время, все замечательно! :good: Но есть нюанс... В решение попадают самые маленькие числа в первую очередь, до больших дело порой не доходт... Мне же нужно наоборот. Скажем, в моем примере 11 выдает как 3+4+4, а мне нужно 7+4.
Объясню проблему.
Есть линия продольной резки рулонного металла. Из рулона надо вырезать полосу ширины, заданной заказчиком. Эта ширина набирается с помощью втулок, располагаемых на валу между двумя ножами. Всего порядка 8 видов(ширин) втулок, разного количества каждого вида, всего их более 90. Так вот порой вместо очевидного решения из 3 широких втулок мне высыпает порядка 50 мелочью. Боюсь, резчик меня не поймет... Можно ли как-то модифицировать алгоритм?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

amk — Sun, 14 Aug 2011 17:54:04 +0000

amk: Если прикидывать вручную, то суммы, которые можно набрать используя числа последовательно

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

3 * *

4 * * * *

4 * * * * * *

7 * * * * * * * * * *

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

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

3 0 1

4 0 1 2 2

4 0 1 2 2 3 3

7 0 1 2 2 3 4 3 4 4 4

Тогда можно получить что
8 - a[3] = 4; 4 - a[2] = 0
10 - a[4] = 3; 3 - a[1] = 0

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Sun, 14 Aug 2011 17:18:58 +0000

Swetlana: Молодец, Сержик, +1 :D
Баг в программе. Щас исправлю старое сообщение, потом в этом отпишу, в чём ошибка.

В программе баг находился в строчке
for i := 1 to N do T[i, 0] := 0;
Правильно
for i := 1 to N do T[i, 0] := 1;
Нулевой вес всегда можно набрать, при любом количестве предметов, поэтому функция T принимает значение 1.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Сержик — Sun, 14 Aug 2011 17:17:55 +0000

Сержик: Буду весьма признателен! Бьюсь уже давно... Я абсолютно согласн с Вами, что здесь не нужен рюкзак. Задача, кстати, абсолютно практическая. Поэтому спасибо заранее за помощь!

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Sun, 14 Aug 2011 17:04:55 +0000

Swetlana: Ага, не работает :(
Нужно вспоминать и разбираться, т.к. вообще-то ДП не пользуюсь.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Сержик — Sun, 14 Aug 2011 16:48:51 +0000

Сержик: Да, программу на паскале с динамическим программированием.
Простейший пример: массив 3 4 4 7(N=4), надо набрать поближе к 9.
Получим 7, а надо бы 8... В таблице T получаем две одинаковых строки(i=2,3)...

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Sun, 14 Aug 2011 16:31:50 +0000

Swetlana: Сержик, вы какой алгоритм имеете в виду? программу на паскале с динамическим программированием?
Приведите набор исходных данных, на котором она не работает

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Сержик — Sun, 14 Aug 2011 16:15:47 +0000

Сержик: Спасибо огромнейшее, Светлана, за алгоритм! :good: Вот только если в массиве есть одинаковые числа, он не работает... :( Может подскажете выход?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Wed, 11 Aug 2010 05:49:56 +0000

Swetlana: Вот лекции Котова, стр.17, пример №1 "Имеется 5 неделимых предметов..."

Лекции_Котова_по_ДП.doc (, : 4072)

Там есть опечатка, на стр.17 :)
Написано

Цитата

T(i,0)=0 при i≥1. {всегда можно набрать нулевую массу}

А должно быть
T(i,0)=1 при i≥1. {всегда можно набрать нулевую массу}

И, соответственно, в коде нужно исправить

Цитата

for i := 1 to 5 do T[i, 0] := 0;

на
for i := 1 to 5 do T[i, 0] := 1;

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Wed, 11 Aug 2010 05:45:45 +0000

Swetlana: Готово дело :)
Тестовый пример топикстартёра. Набираем вес 90, но в ответе ближайшая сумма - 89.
Немного переделала прожку из Котова "Лекции по динамическому программированию".

const N=5;

Ves=90;

var

M: array[1..N]of integer;

T:array[0..N,0..Ves]of byte;

sum,i,j:integer;

begin

M[1]:= 35; M[2]:= 30; M[3]:= 17; M[4]:= 13;

M[5]:= 11;

T[0,0] := 1;

for j := 1 to Ves do T[0, j] := 0;

for i := 1 to N do T[i, 0] := 1;

for i := 1 to N do begin

for j := 1 to Ves do begin

if j >= M[i] then begin

if T[i - 1, j]> T[i - 1, j - M[i]] then

T[i,j]:= T[i - 1, j]

else T[i, j]:= T[i - 1, j - M[i]];end

else T[i, j]:= T[i - 1, j];

end;

for j:=Ves downto 1 do

begin

sum:=j;

if T[N, j] = 1 then

begin

for i := N downto 1 do

begin

if T[i, sum] = T[i - 1, sum] then

writeln (i, '---No')

else begin writeln (i, '---Yes');

sum := sum - M[i];

end;

break;

end;

readln;

end.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Akina — Wed, 11 Aug 2010 05:19:29 +0000

Akina:

Цитата Swetlana @ 11.08.10, 05:06

у суммы и рюкзака питасы разные, у суммы для той же точности она побыстрее будет.

ИМХО если чистка кода для рюкзака выполнена верно и полностью - он просто обязан превратиться в код для суммы.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Wed, 11 Aug 2010 05:06:00 +0000

Swetlana: Благодаря топикстартёру пишу (для себя, конечно :) ) набор суммы дин. программированием. Почти дописала.

Почему я так бьюсь за то, что нужно решать не как рюкзак. Если веса отдельных элементов и, соответственно B очень большие, то для такой задачи нужна PTAS - полиномиальная апроксимационная схема. У которой чем меньше погрешность, тем больше время. А у суммы и рюкзака питасы разные, у суммы для той же точности она побыстрее будет.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Akina — Wed, 11 Aug 2010 05:00:51 +0000

Akina:

Цитата Swetlana @ 10.08.10, 20:57

Зачем её сводить к более общей задаче, мне не очень понятно.

Проще найти код (да хоть у википедиков). Прочём переборные коды весьма компактны... и повыкидывать из них всё лишнее.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Pavlovsky — Wed, 11 Aug 2010 03:55:44 +0000

Pavlovsky: Очень советую реашть задачу псевдополиномиальным алгоритмом.
Скажем, дано 90 сек. Даны кусочки: 35, 30, 17, 13, 11.

1) Создаешь массив A[90]

2) Берешь очередное число, скажем 35

3) Помечаешь A[35]=1

4) Берешь следующее число, скажем 30

5) Помечаешь A[30]=1

6) Перебераешь все элементы массива помеченные единицей и помечаешь A[35+30]=1

7) И так далее

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

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Tue, 10 Aug 2010 20:57:17 +0000

Swetlana: 1. 10 штук можно сделать перебором, например, алгоритмом с возвратом (бэктрэкинг).

2. 20 штук тоже перебором можно сделать, но не уложитесь в указанное время.
Нужно делать динамическим программированием. Вычислительная сложность алгоритма O(nB), где n - количество слагаемых, B - набираемая сумма.

3. Если B - слишком большое, то вначале масштабируют, затем применяют динамическое программирование(Кормен). Метод заключается в уменьшении всех заданных величин s(a) и B в scale раз, где scale – коэффициент масштабирования, и последующим округлением до целого путем отбрасывания дробной части. Величина погрешности полученного таким образом решения не превосходит n*scale.

Куда махнуть рукой... Только в сторону Кормена.
В Кормене она называется Задача о сумме подмножеств Может, гуглить не Сумма размеров, а Сумма подмножеств?
Я для такой размерности особо ничего не искала, т.к. у меня размерность была сверхбольшая. Но знаю, что все методы для такой размерности основаны на динамическом программировании, в Кормене этот подход описан.

to Akina
Рюкзак тоже решается динамическим программированием, сумма размеров - частный случай, класс обеих задач - псевдополиномиальные алгоритмы. Сумма размеров существует как отдельная классическая задача. Зачем её сводить к более общей задаче, мне не очень понятно.

Добавлено 10.08.10, 21:08
Может, и вправду, для суммы размеров найти труднее, чем для рюкзака. :)
Тогда пособие для студентов МФТИ, там для рюкзака есть схема с масштабированием.
Кузюрин, Фомин
Эффективные алгоритмы и сложность вычислений

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Akina — Tue, 10 Aug 2010 20:11:50 +0000

Akina: Ищите рюкзак и считайте вес=стоимость.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Kernel Panic — Tue, 10 Aug 2010 19:52:01 +0000

Kernel Panic: так и есть, у меня только "вес" есть (время). Если размерностью вы имеете в виду размер массива, то там порядка 10-20 штук. Пишется на яваскрипте, должно уложиться в 0,40 с (а желательно меньше). В инете по "сумме размеров" практического алгоритма особо не нашёл. Не махнёте рукой, где смотреть?

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Swetlana — Tue, 10 Aug 2010 16:31:37 +0000

Swetlana: Это не задача о рюкзаке. Рюкзак двупараметрический - вес, стоимость. В задаче о рюкзаке есть ограничение на размер суммарного веса и требуется найти выборку максимальной стоимости.

Это NP-полная задача "Сумма размеров".
1. Если размерность "средняя", то в Кормене описан приближённый алгоритм, на основе динамического программирования, по-моему.
2. Если размерность большая и сверхбольшая, могу дать свой собственный алгоритм, опубликованный в журнале "Мехатроника, автоматизация, управление". Я им отгружала готовую листопрокатную продукцию, набирала заданный вес пачками известного веса при заданной погрешности.

Сумма чисел в массиве, наиболее приближающаяся к необходимой

esperanto — Tue, 10 Aug 2010 15:02:00 +0000

esperanto: задача класса нп или п-спейс, не помню точно, можно решать перебором

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Kernel Panic — Tue, 10 Aug 2010 13:33:51 +0000

Kernel Panic: дальше разберусь, спасибо большое!

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Akina — Tue, 10 Aug 2010 13:28:20 +0000

Akina: Задача о рюкзаке

Сумма чисел в массиве, наиболее приближающаяся к необходимой

Kernel Panic — Tue, 10 Aug 2010 13:18:50 +0000

Kernel Panic: По идее должно быть просто, быстрый поиск в инете не дал результатов (не могу сформулировать точно).

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

Скажем, дано 90 сек. Даны кусочки: 35, 30, 17, 13, 11. Если заполнять от больших к малым, получится 35 + 30 + 17 = 82. Эффективнее же было бы: 35 + 30 + 13 + 11 = 89.

Думаю, задача классическая, если что, скажите название (по-русски/английски), дальше сам разберусь, просто нет времени изобретать велосипед.

Спасибо.