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

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

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

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

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

Спасибо.

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

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

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

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

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

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

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

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

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

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

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

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

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

Очень советую реашть задачу псевдополиномиальным алгоритмом.
Скажем, дано 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 @ 10.08.10, 20:57

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

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

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

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

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

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

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

Готово дело
Тестовый пример топикстартёра. Набираем вес 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;
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;
        end;
      break;  
    end;
end;
 
readln;
end.

Сообщение отредактировано: Swetlana - 14.08.11, 17:20

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

Прикреплённый файлЛекции_Котова_по_ДП.doc (596 Кбайт, скачиваний: 3945)

Там есть опечатка, на стр.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 - 17.08.11, 06:54

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

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

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

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

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

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

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

Сообщение отредактировано: Swetlana - 14.08.11, 17:22

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

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

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

                      1                    
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
  0
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

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

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

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

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

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

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

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

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

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

Для задачи с одной полосой.
В новой постановке ширину можно набирать хоть с недостатком, хоть с избытком, лишь бы отклонение от заданной суммы было минимальным. Для этого вводим допустимое отклонение 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;
    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;
      end;
 
    readln;
    end.

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

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

Задача о наборе суммы минимальным числом заданных слагаемых тоже решается ДП.
Подробности здесь, сообщения №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

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

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

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

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

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

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-му документу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Есть числа:

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

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

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

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

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

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

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

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

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

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

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

Но возникла проблема, встречаются суммы округлённые до сотых, соответственно появляется допуск (применительно к использованному алгоритму 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;
    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;
      end;
 
    readln;
    end.

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

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

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

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

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

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

Цитата

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

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

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

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

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

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