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

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

Да, программу на паскале с динамическим программированием.
Простейший пример: массив 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. Если существует лучшее решение с избытком, оно будет найдено.