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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прикреплённая картинка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сообщение отредактировано: Swetlana - 23.11.12, 14:06