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

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